福州大学第十二届程序设计竞赛 Problem G Escape

Love The Way You Lie 2022-08-05 12:08 167阅读 0赞

**Problem G Escape**

### Accept: 57 Submit: 429   Time Limit: 1000 mSec Memory Limit : 32768 KB ###

## ![prodesc.gif][] Problem Description ##

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

## ![prodesc.gif][] Input ##

有多组测试数据。

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

接下来是T组例子。

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

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

S代表小明的所在地。

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

.代表可以行走的地方。

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

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

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

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

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

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

## ![prodesc.gif][] Output ##

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

## ![prodesc.gif][] Sample Input ##

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

## ![prodesc.gif][] Sample Output ##

YesNoYes

#include <cstdio>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    
    #define Inf 0x7fffffff
    
    char ch[1100][1100], ch1[1100][1100];
    int vv[1100][1100];
    int n, m;
    typedef struct ma
    {
        int x, y;
        int dep;
    }ma;
    typedef struct pot
    {
        int x, y;
        int t;
    }pot;
    bool val[1100][1100];
    int dre[4][2]={ {0,1},{0,-1},{1,0},{-1,0} };
    
    int Min(int a, int b)
    {
        return a>b?b:a;
    }
    
    void gogogo(char s[][1100])
    {
        queue<pot>P;
        pot now, next;
    
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
            {
                if( s[i][j]=='!' ) {
                    now.x=i; now.y=j; now.t=0;
                    P.push(now);
                }
            }
        for(int i=0; i<n; i++)   strcpy(ch1[i], s[i]);
        while( !P.empty() ){
            now = P.front(); P.pop();
    
            for(int i=0; i<4; i++){
                next.x=now.x+dre[i][0];   next.y=now.y+dre[i][1];
                if( next.x<0 || next.x>=n || next.y<0 || next.y>=m ) continue;
                if( ch1[next.x][next.y]=='!' || ch1[next.x][next.y]=='#' ) continue;
                if( ch1[next.x][next.y]=='E') {vv[next.x][next.y]=Min(vv[next.x][next.y], now.t+1); }
                if( ch1[next.x][next.y]=='.') {
                    ch1[next.x][next.y]='!';
                    vv[next.x][next.y] = now.t+1;
                    next.t=now.t+1;
                    P.push(next);
                }
            }
        }
    
    }
    
    int judge(int x, int y, int t)
    {
        if(x<0 || x>=n || y<0 || y>=m) return 0;
        if(ch[x][y]=='!' || ch[x][y]=='#' || val[x][y]) return 0;
        if( t>=vv[x][y] && ch[x][y]!='E' ) return 0;
        return 1;
    }
    
    int bfs()
    {
        int x, y;
        ma now, next;
        queue<ma>Q;
    
        memset( val, false, sizeof(val) );
        for(int i=0; i<n; i++) for(int j=0; j<m; j++) if(ch[i][j]=='S') x=i, y=j;
        now.x=x;  now.y=y;  now.dep=0;
        val[x][y]=true;
    
        Q.push(now);
    
        while( !Q.empty() ){
            now = Q.front(); Q.pop();
            if( ch[now.x][now.y]=='E' && (vv[now.x][now.y]>=now.dep || vv[now.x][now.y]==Inf) )    return now.dep;
    
    
            for(int i=0; i<4; i++){
                next.x=now.x+dre[i][0]; next.y=now.y+dre[i][1];
                if( judge(next.x, next.y, now.dep+1) ){
    
                    next.dep=now.dep+1;
                    Q.push( next );
                    val[next.x][next.y]=true;
                }
            }
        }
        return -1;
    }
    
    int main()
    {
        int t;
        int ans;
        scanf("%d", &t);
        while( t-- ){
            scanf("%d%d", &n, &m);
    
            for(int i=0; i<n; i++)  scanf("%s", ch[i]);
    
            for(int i=0; i<n; i++)
                for(int j=0; j<m; j++) { if( ch[i][j]=='!' ) vv[i][j]=0; else vv[i][j]=Inf; }
    
            gogogo(ch);
            ans = bfs();
    
            if(ans!=-1)
                printf("Yes\n");
            else
                printf("No\n");
        }
    
        return 0;
    }

[prodesc.gif]: http://acm.fzu.edu.cn/image/prodesc.gif