10.起火迷宫()-其他

10.起火迷宫()

原题链接：acwing.com/problem/content/submission/4227/

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
#define x first
#define y second
const int N=1010;
int n,m;
char g[N][N];
PII st2;
vector<PII> nums;
int dist1[N][N],dist2[N][N];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int ans;

void bfs1()
{
    queue<PII> q;
    memset(dist1,0x3f,sizeof dist1);
    for(auto st1:nums)
    {
        q.push(st1);
        dist1[st1.x][st1.y]=0;
    }
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=dx[i]+t.x,y=dy[i]+t.y;
            if(x<0||x>=n||y<0||y>=m||g[x][y]!='.') continue;
            if(dist1[x][y]==0x3f3f3f3f){
                dist1[x][y]=dist1[t.x][t.y]+1;
                q.push({x,y});
            }
        }
    }
}

int bfs2()
{
    queue<PII> q;
    q.push(st2);
    memset(dist2,0x3f,sizeof dist2);
    dist2[st2.x][st2.y]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t.x==0||t.x==n-1||t.y==0||t.y==m-1){
            if(dist2[t.x][t.y]+1<=dist1[t.x][t.y])
                return dist2[t.x][t.y]+1;
        }
        for(int i=0;i<4;i++)
        {
            int x=dx[i]+t.x,y=dy[i]+t.y;
            if(x<0||x>=n||y<0||y>=m||g[x][y]!='.') continue;
            if(dist2[x][y]==0x3f3f3f3f){
                if(dist2[t.x][t.y]+1>=dist1[x][y]) continue;
                dist2[x][y]=dist2[t.x][t.y]+1;
                q.push({x,y});
            }
        }
    }
    return -1;
}

int main()
{
    int tt;
    cin>>tt;
    while(tt--)
    {
        scanf("%d%d",&n,&m);
        nums.clear();
        ans=0x3f3f3f3f;
        for(int i=0;i<n;i++)
            scanf("%s",g[i]);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(g[i][j]=='F') nums.push_back({i,j});
                else if(g[i][j]=='J') st2={i,j};
            }
        bfs1();
        int t=bfs2();
        if(t==-1) puts("IMPOSSIBLE");
        else printf("%d\n",t);
    }
    return 0;
}

原题链接：acwing.com/problem/content/submission/4227/

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
#define x first
#define y second
const int N=1010;
int n,m;
char g[N][N];
PII st2;
vector<PII> nums;
int dist1[N][N],dist2[N][N];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int ans;

void bfs1()
{
    queue<PII> q;
    memset(dist1,0x3f,sizeof dist1);
    for(auto st1:nums)
    {
        q.push(st1);
        dist1[st1.x][st1.y]=0;
    }
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=dx[i]+t.x,y=dy[i]+t.y;
            if(x<0||x>=n||y<0||y>=m||g[x][y]!='.') continue;
            if(dist1[x][y]==0x3f3f3f3f){
                dist1[x][y]=dist1[t.x][t.y]+1;
                q.push({x,y});
            }
        }
    }
}

int bfs2()
{
    queue<PII> q;
    q.push(st2);
    memset(dist2,0x3f,sizeof dist2);
    dist2[st2.x][st2.y]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t.x==0||t.x==n-1||t.y==0||t.y==m-1){
            if(dist2[t.x][t.y]+1<=dist1[t.x][t.y])
                return dist2[t.x][t.y]+1;
        }
        for(int i=0;i<4;i++)
        {
            int x=dx[i]+t.x,y=dy[i]+t.y;
            if(x<0||x>=n||y<0||y>=m||g[x][y]!='.') continue;
            if(dist2[x][y]==0x3f3f3f3f){
                if(dist2[t.x][t.y]+1>=dist1[x][y]) continue;
                dist2[x][y]=dist2[t.x][t.y]+1;
                q.push({x,y});
            }
        }
    }
    return -1;
}

int main()
{
    int tt;
    cin>>tt;
    while(tt--)
    {
        scanf("%d%d",&n,&m);
        nums.clear();
        ans=0x3f3f3f3f;
        for(int i=0;i<n;i++)
            scanf("%s",g[i]);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(g[i][j]=='F') nums.push_back({i,j});
                else if(g[i][j]=='J') st2={i,j};
            }
        bfs1();
        int t=bfs2();
        if(t==-1) puts("IMPOSSIBLE");
        else printf("%d\n",t);
    }
    return 0;
}