学步园

这有一个迷宫，有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,1

0表示道路，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<cstdio>
#include<queue>
#include<utility> 
using namespace std;
const int INF = 100000000;
typedef pair <int,int> P;  //头文件utility。
int maze[9][9]={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,1
};
int N,M;
int sx,sy;
int gx,gy;
int d[100][100];
int bfs()
{
	int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
	queue<P>que;
	for(int i=0;i<9;i++)
	 for(int j=0;j<9;j++)
	  d[i][j]=INF;
	 que.push(P(sx,sy));
	 d[sx][sy]=0;
	 while(que.size()){//不断循环直到队列长度为0。
	 	P p=que.front();que.pop();//从队列最前端取出元素。
		 if(p.first==gx&&p.second==gy)break;//如果取出的状态等于终点，终止搜索。
	    for(int i=0;i<4;i++){
	    	int nx=p.first+dx[i],ny=p.second+dy[i];
	     if(nx>=0&&nx<8&&ny>=0&&ny<8&&maze[nx][ny]!=1&&d[nx][ny]==INF){//（d[nx][ny]!=IEF就代表该点已经访问过）
	      que.push(P(nx,ny));//如果满足以上条件，入队。
	      d[nx][ny]=d[p.first][p.second]+1;//该点位置确定为p点位置+1。
		 }
		}
	 }
	 return d[gx][gy];
}
int main()
{
	int bfs();
	int t;
	scanf("%d",&t);
	while(t--){
	  scanf("%d%d%d%d",&sx,&sy,&gx,&gy);
	  int res=bfs();
	  printf("%d\n",res);
	}
	return 0;
}