题目描述

XYY最近收到了一个迷宫地图，它是由0或者1组成。

0,0,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

0,1,1,1,1,1,1,0,0

“0”表示道路，“1”表示墙，坐标（0<=n<=8）(0<=m<=8)

在迷宫中，只能上下左右移动。为了更好地研究这张地图，需要知道从地图中的一点到另一点的最小距离。

输入

第一行输入一个T，表示有T组测试数据。

随后T行中每行给出n1,m1,n2,m2，分别表示起点的坐标和终点的坐标。

输出

输出最少的步数，若到达不了，输出“YY” 。

样例输入

3
3 1 5 7
3 1 6 7
0 0 8 0

样例输出

12
11
YY

来源

BoilTask

 

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int maze[9][9]={{0,0,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},
				{0,1,1,1,1,1,1,0,0}};
int sx,sy;
int gx,gy;
int d[9][9];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int bfs(){
	queue<P> que;
	for(int i=0;i<9;i++)
		for(int j=0;j<9;j++)
		    d[i][j]=INT_MAX;                   //bfs模板 
			que.push(P(sx,sy));
			d[sx][sy]=0;
			while(que.size()){
				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(0<=nx&&nx<9&&0<=ny&&ny<9&&maze[nx][ny]!=1&&d[nx][ny]==INT_MAX){
						que.push(P(nx,ny));
						d[nx][ny]=d[p.first][p.second]+1;
					}
				}
			}
   return d[gx][gy];		
}


int main(){
	int t;
        cin>>t;
    while(t--){
    cin>>sx>>sy>>gx>>gy;   //输入起点终点 
        if(bfs()<=80)          //这个值有点邪乎，假如全部都是路，左上角走到右下角最多才80步 
	cout<<bfs()<<endl;     //假如能从起点走到终点，、bfs是会返回具体的坐标的； 
	else
	cout<<"YY"<<endl;	    //假如走不到，返回的就是一个地址值（10位）,肯定很大一个数了 
}	return 0;
}