最少步数
- 描述
-
这有一个迷宫，有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
CODE:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
char g[10][10]={"111111111","100100101","100110001","101011011","100001001","110101001","110101001","110100001","111111111"};
int dir[4][4]={{-1,0},{0,1},{1,0},{0,-1}};
int cnt;
int used[9][9];
struct node
{
int x,y,count;
}temp,ans;
int main()
{
int t,a,b,c,d,i,j,dx,dy;
scanf("%d",&t);
while(t--)
{
memset(used,0,sizeof(used));
scanf("%d%d%d%d",&a,&b,&c,&d);
queue<node>q//广搜用到队列
temp.x=a;
temp.y=b;
temp.count=0;
q.push(temp);
used[a][b]=1;
while(!q.empty()) //很重要，深搜循环条件
{
ans.x=q.front().x;
ans.y=q.front().y;
ans.count=q.front().count;
q.pop();
if(ans.x==c && ans.y==d) //深搜终止条件，搜到目的点
break;
for( i=0;i<4;i++)
{
if(!used[ans.x+dir[i][0]][ans.y+dir[i][1]]&& (ans.x+dir[i][0])>=0
&& (ans.x+dir[i][0])<=8 && (ans.y+dir[i][1])>=0
&& (ans.y+dir[i][1])<=8&& g[ans.x+dir[i][0]][ans.y+dir[i][1]]=='0') //找出它的所有邻接点
{
used[ans.x+dir[i][0]][ans.y+dir[i][1]]=1;
temp.x=ans.x+dir[i][0];
temp.y=ans.y+dir[i][1];
temp.count=ans.count+1; //搜到下一层count加1
q.push(temp);
}
}
}
printf("%d\n",ans.count);
}
return 0;
}