UVA11624求助
查看原帖
UVA11624求助
551088
FincheuwYggdrasil楼主2022/8/24 14:17

rt这个程序只输出impossible

#include<bits/stdc++.h>
using namespace std;
int n,m,fire[1010][1010],sx,sy,anstep;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
bool visi[1010][1010];
char mapa[1010][1010];
struct pos{
    int x,y,step;
};
void firefs(int x,int y)
{
    memset(visi,0,sizeof(visi));
    visi[x][y] = true;
    queue<pos> q;
    pos p,r;
    r.x = x;
    r.y = y;
    r.step = 0;
    fire[x][y] = 0;
    q.push(r);
    while(!q.empty())
    {
        p = q.front();
        q.pop();
        fire[p.x][p.y] = p.step;
        for(int i = 0;i < 4;i++)
        {
            int xx = dx[i] + p.x;
            int yy = dy[i] + p.y;
            if(xx < 0 || yy < 0 || xx >= n || yy >= m || visi[xx][yy] || mapa[xx][yy] == '#')
                continue;
            visi[xx][yy] = true;
            r.step = p.step + 1;
            r.x = xx;
            r.y = yy;
            fire[r.x][r.y] = min(r.step,fire[r.x][r.y]);
            q.push(r);
        }
    }
}
void manfs(int x,int y)
{
    memset(visi,0,sizeof(visi));
    visi[x][y] = true;
    queue<pos> q;
    pos p,r;
    r.x = x;
    r.y = y;
    r.step = 0;
    if(fire[x][y] == 0)
        return ;
    q.push(r);
    while(!q.empty())
    {
        p = q.front();
        q.pop();
        for(int i = 0;i < 4;i++)
        {
            int xx = dx[i] + p.x;
            int yy = dy[i] + p.y;
            if(visi[xx][yy] || mapa[xx][yy] == '#' || p.step + 1 > fire[xx][yy])
                continue;

            if(xx < 0 || yy < 0 || xx >= n || yy >= m)
                anstep = min(anstep,p.step+1);
            visi[xx][yy] = true;
            r.step = p.step + 1;
            r.x = xx;
            r.y = yy;
            q.push(r);
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i = 0;i < t;i++)
    {
        scanf("%d%d",&n,&m);
        anstep = 2147483647;
        for(int i = 0;i < n;i++)
            cin >> mapa[i];
        int minn = 2147483647;
        memset(fire,minn,sizeof(fire));
        for(int i = 0;i < n;i++)
        {
            for(int j = 0;j < m;j++)
            {
                if(mapa[i][j] == 'J')
                {
                    sx = i;
                    sy = j;
                }
                if(mapa[i][j] == 'F')
                    firefs(i,j);
            }
        }
        manfs(sx,sy);
        if(anstep == minn)
            printf("IMPOSSIBLE\n");
        else 
            printf("%d\n",anstep+1);
    }
    return 0;
}
2022/8/24 14:17
加载中...