多测挂,单测过qwq
  • 板块UVA11624 Fire!
  • 楼主__AlRTy__
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/11/27 01:20
  • 上次更新2023/10/27 01:17:47
查看原帖
多测挂,单测过qwq
585011
__AlRTy__楼主2022/11/27 01:20

此代码如果每种地图单测可过,但是多测会有几个挂掉,为什么qwq

// #Tyrue#
#include<map>
#include<cstdio>
#include<string>
#include<queue>
#include<string.h>
#include<iostream>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
struct Node{
    int x,y,t;
};
const int N=1e3+10;
int T,n,m,fx,fy,sx,sy;
int fire[N][N];
int dx[5]{0,0,0,1,-1},
    dy[5]{0,1,-1,0,0};
bool vis[N][N];
queue<Node> q;
void bfs_fire(){
    while(!q.empty()){
        Node f=q.front();
        q.pop();
        for(int i=1;i<=4;i++){
            int xx=f.x+dx[i],yy=f.y+dy[i];
            if(f.t+1<fire[xx][yy]){
                fire[xx][yy]=f.t+1;
                q.push((Node){xx,yy,f.t+1});
            }
        }
    }
    return ;
}
void bfs_solve(){
    vis[sx][sy]=1;
    q.push((Node){sx,sy,0});
    int p=0;
    while(!q.empty()){
        Node f=q.front();
        q.pop();
        if(f.x==n || f.y==m || f.x==1 || f.y==1){
            printf("%d\n",f.t+1);
            p=1;
            break ;
        }
        for(int i=1;i<=4;i++){
            int xx=dx[i]+f.x,yy=dy[i]+f.y;
            if(
                f.t+1<fire[xx][yy]
                && !vis[xx][yy]
            ){
                vis[xx][yy]=1;
                q.push((Node){xx,yy,f.t+1});
            }
        }
    }
    if(!p){
        puts("IMPOSSIBLE");
    }
}
int main(){
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    T=read();
    while(T--){
        n=read(),m=read();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                vis[i][j]=0;
                fire[i][j]=n*m;
                char c;
                cin>>c;
                if(c=='J'){
                    sx=i;
                    sy=j;
                }else if(c=='F'){
                    q.push((Node){i,j,0});
                    fire[i][j]=0;
                }else if(c=='#'){
                    fire[i][j]=0;
                }
            }
        }
        bfs_fire();
        bfs_solve();
        // for(int i=1;i<=n;i++){
        //     for(int j=1;j<=m;j++){
        //         printf("%d\t",fire[i][j]);
        //     }
        //     puts("");
        // }
    }   
    return 0;
}
2022/11/27 01:20
加载中...