Input/Output: standard input/output
Ayutthaya was one of the first kingdoms in Thailand, spanning since its foundation in 1350 to its collapse in 1767. The organization of Extraordinary Mystery Investigators (IME, in their language) aims to uncover the secrets of this ancient kingdom. One of IME‘s most notorious historians is Márcio "the indispensable" Himura. He is currently researching the laws and punishments in place during King Ramathibodi I‘s rule. Recent discoveries suggest how Ramathibodi I used to punish the subjects that did not convert to Theravada Buddhism, the religion he adopted.
The punishment involved trapping the accused prisoner in a room with a single exit and to light up a fire. If the prisoner could manage to reach the exit before getting caught on fire, she or he was forgiven and allowed to live. Márcio has access to some records that describe the floorplans of the rooms where this punishment took place. However, there are no documents asserting whether the prisoners were forgiven. Márcio would like to know whether each of these prisoners had any chance at all of having been forgiven. For that, Márcio represented each room as a grid with N rows and M columns, where each position has a symbol with the following meaning
where "start" is the person‘s initial position in the room when fire has been lit up. Moreover, Márcio imposed the following constraints in his model:
You are a member of IME and Márcio would like to know if you deserve your position. He has charged you with the task of determining whether a prisoner had any chance to be forgiven.
The first line has a single integer T, the number if test cases.
Each instance consists of several lines. The first line contains two integers, N and M. Each of the following N lines contains exactly M symbols representing, as described above, a room from which the prisoner must escape.
Limits
For each instance, print a single line containing a single character. Print Y if the prisoner had any chance of being forgiven; otherwise, print N.
Input 3 4 5 ....S ..... ..... F...E 4 4 ...S .... .... F..E 3 4 ###S #### E..F Output Y N N
题意：S是起点，E是起点，F是火，#是墙，.是路，人从起点跑向终点，碰到火立刻死亡（即使人在终点与火相遇，也不能出去），人每分钟移动一个格子，火每分钟向上下左右四个方向蔓延一个格子，问人是否能跑出去，能输出Y，否则输出N。
两次广搜，第一次先记录火蔓延到每个格子的时间，然后搜索人跑出去的时间。
附上代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <queue> 6 #define MP make_pair 7 using namespace std; 8 char maps[1005][1005]; 9 int n,m; 10 int vis[1005][1005]; 11 int ss[1005][1005]; ///记录火的蔓延速度 12 int s[1005][1005]; ///记录人的行走速度 13 int dx[]={1,0,-1,0}; 14 int dy[]={0,1,0,-1}; 15 16 bool judge(int x,int y) 17 { 18 if(x>=1 && x<=n && y>=1 && y<=m) return 1; 19 return 0; 20 } 21 22 void BFS(int x,int y) ///搜索人到达终点的时间 23 { 24 int i; 25 queue< pair<int,int> > q; 26 memset(s,-1,sizeof(s)); 27 s[x][y]=0; 28 q.push(MP(x,y)); 29 while(!q.empty()) 30 { 31 x=q.front().first; 32 y=q.front().second; 33 q.pop(); 34 if(maps[x][y]==‘E‘) 35 { 36 // cout<<s1.t<<endl; 37 printf("Y\n"); 38 return; 39 } 40 for(i=0; i<4; i++) 41 { 42 int xx=x+dx[i]; 43 int yy=y+dy[i]; 44 if(judge(xx,yy)&&s[xx][yy] ==-1&&maps[xx][yy]!=‘#‘&&s[x][y]+1<ss[xx][yy]) ///人到达这个点一定要比火快，才能走 45 { 46 s[xx][yy]=s[x][y]+1; 47 q.push(MP(xx,yy)); 48 } 49 } 50 } 51 printf("N\n"); 52 return; 53 } 54 55 void BFS2() ///搜索火的蔓延速度 56 { 57 queue< pair<int,int> >qq; 58 int i,j; 59 for(i=1; i<=n; i++) 60 for(j=1; j<=m; j++) 61 if(maps[i][j]==‘F‘) 62 { 63 ss[i][j]=0; 64 qq.push(MP(i,j)); 65 } 66 while(!qq.empty()) 67 { 68 int x=qq.front().first; 69 int y=qq.front().second; 70 qq.pop(); 71 for(int i=0; i<4; i++) 72 { 73 int xx=x+dx[i]; 74 int yy=y+dy[i]; 75 if(judge(xx,yy)&&maps[xx][yy]!=‘#‘&&ss[xx][yy]==-1) 76 { 77 ss[xx][yy]=ss[x][y]+1; 78 qq.push(MP(xx,yy)); 79 } 80 } 81 } 82 return; 83 } 84 int main() 85 { 86 int i,j,T; 87 int a1,b1; 88 scanf("%d",&T); 89 getchar(); 90 while(T--) 91 { 92 scanf("%d%d",&n,&m); 93 memset(vis,0,sizeof(vis)); 94 for(i=1; i<=n; i++) 95 for(j=1; j<=m; j++) 96 ss[i][j]=-1; 97 int w=0; 98 for(i=1; i<=n; i++) 99 { 100 getchar(); 101 for(j=1; j<=m; j++) 102 { 103 scanf("%c",&maps[i][j]); 104 if(maps[i][j]==‘S‘) 105 { 106 a1=i; 107 b1=j; 108 } 109 } 110 } 111 BFS2(); 112 BFS(a1,b1); 113 } 114 return 0; 115 116 }
bnu 52037 Escape from Ayutthaya
原文：http://www.cnblogs.com/pshw/p/5698702.html