最少步数
时间限制：3000 ms | 内存限制：65535 KB
难度：4
- 描述
这有一个迷宫，有0~8行和0~8列：
1,1,1,1,1,1,1,1,1
1,0,0,1,0,0,1,0,1
1,0,0,1,1,0,0,0,1
1,0,1,0,1,1,0,1,1
1,0,0,0,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,0,0,0,1
1,1,1,1,1,1,1,1,10表示道路，1表示墙。
现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？
（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）
- 输入
- 第一行输入一个整数n（0<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。 - 输出
- 输出最少走几步。
- 样例输入
2
3 1 5 7
3 1 6 7- 样例输出
12
11
代码一：写的复杂了#include<stdio.h>
#include<string.h>
#include<queue> using namespace std; #define N 9 int maze[N][N]={,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,};
int mazeH[N][N]; struct Node
{
int x,y,cnt; };
int dir[][]={{,},{,-},{,},{-,}};//定义方向 bool Judge(int x,int y)
{
return (x < N && x >= && y < N && y >= && !mazeH[x][y])?true:false;//如果没有超出边界，返回true，否者false } void MakeNode(int x,int y,int cnt,Node &node)
{
node.x=x;
node.y=y;
node.cnt=cnt;
mazeH[x][y]=;
} int bfs(int sX,int sY,int eX,int eY)
{
Node node,tempNode;
MakeNode(sX,sY,,node);
queue<Node> Q;
Q.push (node);
while( !Q.empty() )
{
node=Q.front();
Q.pop ();
if( node.x==eX && node.y==eY )//判断是否找到结束的那个点，如果找到了，将返回最小步数；
{
return node.cnt;
}
for(int i=;i<;++i)
{
if( Judge(node.x+dir[i][],node.y+dir[i][]) )
{
MakeNode(node.x+dir[i][],node.y+dir[i][],node.cnt+,tempNode);
Q.push (tempNode);
}
}
}
} int main()
{
int nCases;
scanf("%d",&nCases);
while( nCases-- )
{
int sX,sY,eX,eY;
scanf("%d%d%d%d",&sX,&sY,&eX,&eY);
memcpy(mazeH,maze,sizeof(maze));//把maze拷贝到mazeH中；
int ans=bfs(sX,sY,eX,eY);//bfs搜索
printf("%d\n",ans);
}
return ;
}代码二：这个简单点
#include<stdio.h>
#define min(x,y) x<y?x:y;
int map[][]={ ,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,,,
,,,,,,,, };
int x1,x2,y1,y2,m;
void dfs(int x,int y,int s)
{
if(map[x][y]) return ;
if(x==x2&&y==y2)
{
m=min(s,m);
return ;
}
s++;
map[x][y]=;
dfs(x+,y,s);
dfs(x-,y,s);
dfs(x,y+,s);
dfs(x,y-,s);
map[x][y]=;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
m=;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
dfs(x1,y1,);
printf("%d\n",m);
}
return ;
}