- 浏览: 143039 次
- 性别:
- 来自: 帝都
文章分类
最新评论
-
jackchen0227:
汗,谢谢啊
joj 1817: Triangle 三角形的判定 -
RootJ:
输出时候没有写:号。。。
joj 1817: Triangle 三角形的判定 -
jackchen0227:
嗯再捡捡。。
不带括号的四则运算 -
ruby_windy:
不是大二实验课写的么...
不带括号的四则运算
这个是来自 国际大学生程序设计竞赛例题解(1)的题目
很简单的一道搜索题目,但是没有使用dfs,
使用的是特殊的bfs,非常巧妙
代码
/*
Qi Shi Wen Ti
similar to eight queens
use bfs() to get the min step
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int queue[1000][2];
int matrix[8][8];
int startX,startY,endX,endY;
int head = -1,tail = 0;
int dir[8][2] = {{-1,-2},{-1,2},{-2,-1},{-2,1},{1,-2},{1,2},{2,-1},{2,1}};
void put(int x,int y)
{
tail ++;
if(tail >= 1000)
tail = tail % 1000;
queue[tail][0] = x;
queue[tail][1] = y;
}
void get(int * x,int * y)
{
head ++;
if(tail < head)
{
printf("queue error!\n");
exit(0);
}
*x = queue[head][0];
*y = queue[head][1];
}
int queueEmpty()
{
return tail < head ? 1:0;
}
/*
the problem is how to calculate the step
it seems like it's hard to find out one step's next step in the bfs search
while it is easy in the dfs search;
standard bfs
*/
void bfs(int startX,int startY,int endX,int endY)
{
int curX,curY;
int minStep=0,step=0;;
put(startX,startY);
while(! queueEmpty())
{
get(&curX,&curY);
matrix[curX][curY] = 1;
if(curX == endX && curY == endY)
{
if(step > minStep)
minStep = step;
}
else if( 1)
{
}
else
{
for(int j=0;j<8;j++)
{
curX += dir[j][0];
curY += dir[j][1];
if(matrix[curX][curY] != 1 && curX >= 0 && curX < 8 && curY > -1 && curY < 8)
put(curX,curY);
}
}
}
}
/*
special Bfs
it visited all nodes in a layer (just a layer's node int bfs tree) in a round
*/
int specialBfs(int startX,int startY,int endX,int endY)
{
int head =0,tail =1,tmpTail;
int step = 0;
int curX = startX,curY = startY;
queue[head][0] = startX;
queue[head][1] = startY;
matrix[curX][curY] = 1;
while(head <tail)
{
step ++;
tmpTail = tail;
for(int i=head;i<tail;i++) //一次访问 整个树的一层节点,非常巧妙
{
for(int j=0;j<8;j++)
{
curX = queue[i][0] + dir[j][0];
curY = queue[i][1] + dir[j][1];
if(matrix[curX][curY] != 1 && curX >= 0 && curX < 8 && curY > -1 && curY < 8)
{
queue[tmpTail][0] = curX;
queue[tmpTail][1] = curY;
tmpTail ++; // here we must add tmpTail after put node in queue
matrix[curX][curY] = 1;
if(curX == endX && curY == endY)
return step;
}
}
}
head = tail;
tail = tmpTail;
}
return -1;
}
int main()
{
freopen("in.txt","r",stdin);
int barrierCount;
char c1,c2;
scanf("%d\n",&barrierCount);
for(int i=0;i<barrierCount;i++)
{
scanf("%c%c ",&c1,&c2);
matrix[c1-'a'][c2-'1'] = 1;
}
scanf("%c%c\n",&c1,&c2);
startX = c1 - 'a';
startY = c2 - '1';
scanf("%c%c\n",&c1,&c2);
endX = c1 - 'a';
endY = c2 - '1';
printf("%d\n",specialBfs(startX,startY,endX,endY));
fclose(stdin);
return 0;
}
发表评论
-
-在二元树中找出和为某一值的所有路径--捡捡递归的使用
2012-03-30 21:05 886/* 算法要求:打印从root到叶节点的路径上的权值和 为 ... -
不带括号的四则运算
2011-10-09 21:24 1416/* 不带括号的表达式的四则运算 使用两个堆栈,一个o ... -
[zz]catalan数的分析与应用
2011-06-25 22:09 1197性质 令h(0)=1,h( ... -
joj 1085: I Think I Need a Houseboat 半圆形侵蚀
2011-06-24 20:54 9361085: I Think I Need a Ho ... -
joj 1032 deck 重心的计算
2011-06-24 19:12 10931032: Deck Result TIME ... -
joj 1186 Box of Bricks 水题
2011-06-19 09:46 9241186: Box of Bricks Re ... -
***joj 1026 the staircase 利用递归、动态规划和一道类似题目
2011-06-18 19:27 1258转自网易何国涛的博客http://zhedahht.bl ... -
joj 1062 Computer Versus Mankind 非递归最大公约数 最小公倍数
2011-06-18 15:15 12121062: Computer Versus Mankin ... -
基本的排序:非递归的堆排序
2011-06-17 15:38 0void restore(int root,int le ... -
joj 1817: Triangle 三角形的判定
2011-06-15 20:34 12751817: Triangle Result ... -
×joj 1175 The Binomial Function 递归,递归优化,非递归
2011-06-15 19:32 8351175: The Binomial Functio ... -
joj 1146 标准输入+字符串反转
2011-06-15 18:02 11271146: Word Reversal Re ... -
joj 1149Binary Number 二进制移位操作
2011-06-15 09:50 9211149: Binary Numbers R ... -
joj 2484
2011-06-14 13:35 8092484: Chinese Character A ... -
**joj:1017 fire net 递归回溯的使用
2011-06-14 12:35 10561017: Fire Net Res ... -
joj 1014 the matrix 从八个方向遍历访问矩阵
2011-06-10 20:51 11671014: The Matrix Re ... -
joj 1013 Polynomial Multiplication多项式乘法的计算
2011-06-10 19:54 12891013: Polynomial Multiplic ... -
[zz] c 与 c++ 中的内存分配
2011-06-08 21:45 1297C语言跟 ... -
new 与malloc的区别
2011-06-08 21:24 2407学过C++和C语言的一般都会对编程语言中的内存分配有点小困 ... -
joj 2749 大数比较大小与减法
2011-06-08 16:32 1896/* 题目不难,一个大 ...
相关推荐
分治法解决骑士巡游问题。.NET中实现。fin66,fin68,fin88,fin810,fin1010,fin1012为读入文件,output为a的读出文件。本算法适用于m,n>=12且|m-n|的情况。并且Hamilton回路为结构化回路。
输入棋盘大小NxN 以及初始位置 程序会运行得到有力方法,用棋盘输出
骑士飞行棋----这个还可以吗,骑士飞行棋----这个还可以吗
凭借骑士网络的不断创新精神和认真的工作态度,骑士人才系统已成国内同类软件中的最好用的人才系统。系统特点:功能模块专业、布局严谨科学以现有成功人才网站为局部参考,并充分结合人才网站的特点与商业模式进行...
经典的骑士遍历算法,可以设置棋盘的大小,结果返回骑士的遍历路线
骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令骑士GM命令...
用C++写的简单的骑士问题,写的一般,望指教。
骑士飞行棋--ACCp5.0 Java项目
算法设计与分析课程设计论文-骑士问题、图着色问题、离散帝国竞争算法。 骑士问题、图着色问题 给出了详细的C++代码,离散帝国竞争算法给出了详细的算法描述。
骑士问题c++实现,输出解决步骤,源代码
马周游路线问题的两种新解法 acm 算法 poj oi 马周游
骑士游历问题 C# 控制台程序 参考:数据结构java版 电子工业大学出版社
2020饿了么蓝骑士调研报告-饿了么-202004
国王的骑士问题testcase
1. Android Fragment 己 1. Google Maps Android 3. Java 人错发 人
一个用C++写的骑士巡游问题,用递归方法
详细讲解了骑士的任务用队列方法解决的策略,层层深入
2019年度内容行业版权报告-维权骑士-202003.rar
骑士周游问题,采用多种方法解决骑士周游问题,如有其它需要,请留言
2019年度内容行业版权报告-维权骑士-202003.pdf