There are multiple sets of test data.
The first row of each set of test data is an integer T, which represents the number of examples to follow.(0<=T<=10)
Following is an example of Group T.
The first line of each set of examples is two integers, N and M.The size of the labyrinth is represented by N rows and M columns (0<=N, M<=1000).
Next is a labyrinth description of N*M.
S stands for Xiaoming's location.
E stands for export, with only one export.
Represents a place where you can walk.
!Represents the place where magma originated.(There will be more than one such place, the number of which is less than or equal to 10,000)
#stands for a wall in the labyrinth that not only prevents Xiaoming from advancing but also magma from spreading.
Xiao Ming's carrier treasure can only move one space around each second, and Xiao Ming can't touch the magma (Xiao Ming can't be in the same space as the magma).
Magma spreads one space per second to areas that are not walls around it.
Xiao Ming's movement is completed before the magma spreads into the corresponding grid.
Xiao Ming can move to the exit, then Xiao Ming can escape smoothly.
3 5 5 ....! S.... #.... !#... #E... 2 2 S. !E 2 2 SE !.Sample Output
Yes NoYes
/** Bi-directional bfs Push in together when pushing into the fire point Otherwise it will time out Points other than exports arrive before the fire Exports can arrive together **/ #include<stdio.h> #include<string.h> #include<queue> #include<algorithm> #define N 1000*1000 using namespace std; struct data { int x,y; int step; }; int n,m; int sx,sy; char maps[1003][1003]; int dx[4]= {0,0,1,-1}; int dy[4]= {1,-1,0,0}; int vis[1003][1003]; int step[1003][1003]; int fx[10002],fy[10003]; void dfs(int zz) { data f; //printf("%d %d %c\n",f.x,f.y,maps[f.x][f.y]); memset(vis,0,sizeof(vis)); queue<data>q; for(int i=0; i<zz; i++) { f.x=fx[i]; f.y=fy[i]; f.step=0; step[f.x][f.y]=0; q.push(f); vis[f.x][f.y]=1; } while(!q.empty()) { data now; now=q.front(); q.pop(); for(int i=0; i<4; i++) { data s; s.x=now.x+dx[i]; s.y=now.y+dy[i]; s.step=now.step+1; if(s.x<=n&&s.x>0&&s.y<=m&&s.y>0&&maps[s.x][s.y]!='#'&&vis[s.x][s.y]==0) { //printf("%d %d %c\n",s.x,s.y,maps[s.x][s.y]); q.push(s); vis[s.x][s.y]=1; step[s.x][s.y]=min(s.step, step[s.x][s.y]); } } } } int dfs2() { data f; f.x=sx; f.y=sy; f.step=0; memset(vis,0,sizeof(vis)); queue<data>q; q.push(f); vis[f.x][f.y]=1; while(!q.empty()) { data now; now=q.front(); q.pop(); // printf("%c\n",maps[now.x][now.y]); if(maps[now.x][now.y]=='E') return 1; for(int i=0; i<4; i++) { data s; s.x=now.x+dx[i]; s.y=now.y+dy[i]; s.step=now.step+1; if(s.x<=n&&s.x>0&&s.y<=m&&s.y>0&&maps[s.x][s.y]!='#'&&vis[s.x][s.y]==0) { if(s.step<step[s.x][s.y]) { q.push(s); vis[s.x][s.y]=1; } else if(s.step==step[s.x][s.y]&&maps[s.x][s.y]=='E') return 1; } } } return 0; } int main() { int t; scanf("%d",&t); while(t--) { int zz=0; scanf("%d%d",&n,&m); memset(maps,' ',sizeof(maps)); memset(step,N,sizeof(step)); for(int i=1; i<=n; i++) { scanf("%s",maps[i]+1); for(int j=1; j<=m; j++) { if(maps[i][j]=='S') { sx=i; sy=j; } if(maps[i][j]=='!') { fx[zz]=i; fy[zz++]=j; } } } dfs(zz); int f=dfs2(); if(f) printf("Yes\n"); else printf("No\n"); } }