Escape-白红宇

Escape

阅读量：7077 次

发布时间：2019-06-28

本文共 1921 字，大约阅读时间需要 6 分钟。

小明进入地下迷宫寻找宝藏，找到宝藏后却发生地震，迷宫各处产生岩浆，小明急忙向出口处逃跑。如果丢下宝藏，小明就能迅速离开迷宫，但小明并不想轻易放弃自己的辛苦所得。所以他急忙联系当程序员的朋友你（当然是用手机联系），并告诉你他所面临的情况，希望你能告诉他是否能成功带着宝藏逃脱。

Input

有多组测试数据。

每组测试数据第一行是一个整数T,代表接下去的例子数。（0<=T<=10）

接下来是T组例子。

每组例子第一行是两个整数N和M。代表迷宫的大小有N行M列（0<=N,M<=1000）。

接下来是一个N*M的迷宫描述。

S代表小明的所在地。

E代表出口,出口只有一个。

.代表可以行走的地方。

！代表岩浆的产生地。（这样的地方会有多个,其个数小于等于10000）

#代表迷宫中的墙，其不仅能阻挡小明前进也能阻挡岩浆的蔓延。

小明携带者宝藏每秒只能向周围移动一格，小明不能碰触到岩浆（小明不能和岩浆处在同一格）。

岩浆每秒会向四周不是墙的地方蔓延一格。

小明先移动完成后，岩浆才会蔓延到对应的格子里。

小明能移动到出口，则小明顺利逃脱。

Output

每组测试数据输出只有一行“Yes”或者“No”。 “Yes”代表小明可以成功逃脱。否则输出“No”。

Sample Input

35 5....!S....#....!#...#E...2 2S.!E2 2SE!.

Sample Output

YesNoYes 先进行bfs预处理更新岩浆到每一个‘路’的最短时间；然后bfs找到一条时间最短又不碰到岩浆的路；

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #define INF 0x3f3f3f3fusing namespace std;#define N 1005char Map[N][N];int n, m, f, st[N][N], vis[N][N];int tab[4][2]={ { 0, 1}, { 1, 0}, {-1, 0}, { 0, -1},};struct node{ int x, y, t;};void bfs(){ queue
               
                Q; node q, p; int i, j; for(i=0;i
                
                 =n||p.y<0||p.y>=m||Map[p.x][p.y]=='#'||vis[p.x][p.y]) continue; p.t=q.t+1; st[p.x][p.y]=p.t;///更新岩浆到每一个坐标的时间 vis[p.x][p.y]=1;.///标记 Q.push(p);///压入队列（先进先出） } }}void bfs2(int x, int y){ queue
                 
                  Q; node q, p; q.x=x; q.y=y; q.t=1; Q.push(q); while(Q.size()) { q=Q.front(); Q.pop(); for(int i=0;i<4;i++) { p.x=q.x+tab[i][0]; p.y=q.y+tab[i][1]; if(p.x<0||p.x>=n||p.y<0||p.y>=m||Map[p.x][p.y]=='#'||vis[p.x][p.y]==1) { continue; } if(Map[p.x][p.y]=='E'&&st[p.x][p.y]>=q.t)///同时到出口也算成功 { f=1; return; } if(st[p.x][p.y]&&st[p.x][p.y]<=q.t)///岩浆先到就算不能通行 { continue; } p.t=q.t+1; vis[p.x][p.y]=1; Q.push(p); } }}int main(){ int i, j, T, min1; scanf("%d", &T); while(T--) { int sx,sy; f=0; memset(st,0,sizeof(st)); memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(int i=0;i

转载于:https://www.cnblogs.com/zct994861943/p/7203857.html

你可能感兴趣的文章

设计模式（十）：Decorator装饰者模式 -- 结构型模式