题目描述
一个叫ACM的寻宝者找到了一个藏宝图,它根据藏宝图找到了一个迷宫,不限时间和步数,当然也没有陷阱,请你判断他能不能顺利的得到宝藏。
输入
多组输入
每组测试数据的第一行包含了两个整数M,N$(1<N,M<20)$(n=0&&m=0表示输入结束),分别代表了迷宫的行和列。接下来的M每行有N个字符,描述了迷宫的布局。其中每个字符的含义如下:
.表示可以走的路
S:表示ACM的出发点
G表示宝藏的位置
#表示这里有墙,ACM无法进入或者穿过。
输出
每行输出一个YES表示ACM能找到宝藏,输出NO表示ACM找不到宝藏。
样例输入
1 2 3 4 5 6 7 8 9 10
| 4 4 S.#. ..#. ..#G ..#. 3 4 S.#. ..#. ...G 0 0
|
样例输出
题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| #include <iostream> #include <queue> using namespace std; struct node{ int x; int y; }s,g,Node; int n,m,flag; char a[1000][1000]; int inq[1000][1000]; int X[4]={0,0,1,-1}; int Y[4]={1,-1,0,0}; bool judge(int x,int y){ if(x<0x>=ny<0y>=m)return false; if(a[x][y]=='#'inq[x][y]==true)return false; return true; } void bfs(){ queue<node>f; f.push(s); while(f.empty()!=1){ node top=f.front(); f.pop(); if(top.x==g.x&&top.y==g.y){ flag=1; return; } for(int i=0;i<4;i++){ int newx=top.x+X[i]; int newy=top.y+Y[i]; if(judge(newx,newy)){ Node.x=newx,Node.y=newy; f.push(Node); inq[newx][newy]=true; } } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while(cin>>n>>m){ if(n==0&&m==0)break; flag=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; inq[i][j]=false; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]=='S'){ s.x=i;s.y=j;//记录起点的坐标 }else if(a[i][j]=='G'){ g.x=i;g.y=j;//记录宝藏的坐标 } } } bfs(); if(flag==0)cout<<"NO"<<endl; else if(flag==1)cout<<"YES"<<endl; }
return 0; }
|