GZHU18級寒假訓練：Leo's Trial-G

UVA-11624

• Joe works in a maze. Unfortunately, portions of the maze have

  caught on fire, and the owner of the maze neglected to create a fire

  escape plan. Help Joe escape the maze.

  Given Joe’s location in the maze and which squares of the maze

  are on fire, you must determine whether Joe can exit the maze before

  the fire reaches him, and how fast he can do it.

  Joe and the fire each move one square per minute, vertically or

  horizontally (not diagonally). The fire spreads all four directions

  from each square that is on fire. Joe may exit the maze from any

  square that borders the edge of the maze. Neither Joe nor the fire

  may enter a square that is occupied by a wall.

• Input

  The first line of input contains a single integer, the number of test

  cases to follow. The first line of each test case contains the two

  integers R and C, separated by spaces, with 1 ≤ R, C ≤ 1000. The

  following R lines of the test case each contain one row of the maze. Each of these lines contains exactly

  C characters, and each of these characters is one of:

  • #, a wall

  • ., a passable square

  • J, Joe’s initial position in the maze, which is a passable square

  • F, a square that is on fire

  There will be exactly one J in each test case.

• Output

  For each test case, output a single line containing ‘IMPOSSIBLE’ if Joe cannot exit the maze before the

  fire reaches him, or an integer giving the earliest time Joe can safely exit the maze, in minutes.

• Sample Input

  2

  4 4

  -####

  -#JF#

  -#…#

  -#…#

  3 3

  -###

  -#J.

  -#.F

• Sample Output

  3

  IMPOSSIBLE

這是一個雙重BFS的題，第一個是joe的逃跑路線，第二個是火勢蔓延路線，joe的出始位置一定，起火位置不一定。

#include <iostream>
#include <queue>
#include <memory.h>
#include <stdio.h>
#define MAX 1100
using namespace std;
struct P//用來存儲路徑的節點
{
    int r,c;
    int step;
    P(int _r,int _c,int _s)
    {
        r=_r,c=_c,step=_s;
    }
    P(){}
};
 
const int dr[] = {0,0,1,-1};//構造函數
const int dc[] = {1,-1,0,0};
char Map[MAX][MAX];//存儲地圖
int visit[MAX][MAX];//BFS中最重要的visit數組
int times[MAX][MAX];//記錄每個地方被燒到所需的時間
int r,c;//行，列
int Step;//記錄最終逃脫所需的步數或時間
P J;
queue<P> q;//全局隊列，這是本題的關鍵，也是一個大坑
 
void clear_q()//用來清除隊列中的資料
{
    while(!q.empty())
        q.pop();
}
 
void show_time()//調試使用
{
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            cout<<times[i][j]<<' ';
        }
        cout<<endl;
    }
}
 
void bfs_fire()//預處理，求出每一個位置被燒到所需要花的時間
{
    int i;
    int R,C,Time;
    while(!q.empty())
    {
        P temp=q.front();
        q.pop();
        //cout<<temp.r<<' '<<temp.c<<endl;
        for(i=0;i<4;i++)
        {
            R=temp.r+dr[i];
            C=temp.c+dc[i];
            Time=temp.step+1;
            if(R>=0&&R<r&&C>=0&&C<c&&(Map[R][C]=='.'||Map[R][C]=='J')&&visit[R][C]==0)
            {
                //cout<<R<<' '<<C<<endl;
                visit[R][C]=1;
                q.push(P(R,C,Time));
                times[R][C]=Time;
            }
        }
    }
}
 
 
int bfs_joe()//逃跑路線，每走一個位置，不僅要看是否符合一般條件，還要用到上一步求出的時間
{
    int i;
    int R,C,Time;
    clear_q();
    q.push(J);
    visit[J.r][J.c]=1;
    while(!q.empty())
    {
        P temp=q.front();
        q.pop();
        //cout<<temp.r<<' '<<temp.c<<endl;
        if(temp.r==0||temp.r==(r-1)||temp.c==0||temp.c==(c-1))
        {
            Step=temp.step+1;
            return 1;
        }
        for(i=0;i<4;i++)
        {
            R=temp.r+dr[i];
            C=temp.c+dc[i];
            Time=temp.step+1;
            if(R>=0&&R<r&&C>=0&&C<c&&Map[R][C]=='.'&&visit[R][C]==0&&Time<times[R][C])
            {
                visit[R][C]=1;
                q.push(P(R,C,Time));
            }
        }
    }
    return 0;
}
 
int main()
{
    int i,j;
    int t;
    cin>>t;
    while(t--)
    {
        clear_q();//清空隊列
        cin>>r>>c;
        for(i=0;i<r;i++)
        {
            cin>>Map[i];
            for(j=0;j<c;j++)
            {
                if(Map[i][j]=='F')//本題最最坑爹的地方，題意并沒有直接對着火點的數量進行說明，但确實說了，隐含在portions 這個單詞中，fuck，英文不好真捉急
                {
                    q.push(P(i,j,0));
                    times[i][j]=0;
                    visit[i][j]=1;
                }
                if(Map[i][j]=='J')
                {
                    J.r=i;
                    J.c=j;
                    J.step=0;
                }
            }
        }
 
        for(i=0;i<r;i++)//每個點的初始被燒所需的時間應該設為正無窮
        {
            for(j=0;j<c;j++)
            {
                times[i][j]=1000000007;
            }
        }
        memset(visit,0,sizeof(visit));//visit數組是兩個BFS公用的，是以需要初始化一下
        bfs_fire();
        //show_time();
        memset(visit,0,sizeof(visit));
        if(bfs_joe())
            cout<<Step<<endl;
        else
            cout<<"IMPOSSIBLE"<<endl;
 
    }
    return 0;
}

           

代碼來源：https://blog.csdn.net/wr132/article/details/45399337