样例过了,wa和re都有大佬求调

P1141 01迷宫

zzz987 @ 2024-01-20 10:17:34

#include<iostream>
#include<queue>
using namespace std;
const int N=1e3+9;
int n,m;
int a[N][N];
int p[N][N],d=0;
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
void    dfs(int x,int y){
    for(int i=0;i<4;i++){
        int tx=x+dx[i],ty=y+dy[i];
        if(a[tx][ty]==a[x][y])  continue;
        if(p[tx][ty])   continue;
        if(1<=tx&&tx<=n&&1<=ty&&ty<=m){
            p[tx][ty]=d;
            dfs(tx,ty);
        }
    }
}
int ans[N*N];
int main(){
    cin >>m>>n;
    string s;
    for(int i=1;i<=n;i++){
        cin >>s;
        for(int j=0;j<s.size();j++){
            a[i][j+1]=s[j]-'0';
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(!p[i][j]){   
                p[i][j]=++d;
                dfs(i,j);
                cout <<endl;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int t=p[i][j];
            ans[t]++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            p[i][j]=ans[p[i][j]];
        }
    }
    while(m--){
        int x,y;    cin >>x>>y;
        cout <<p[x][y]<<"\n";
    }
    return 0;
}

by Y_QWQ_Y @ 2024-01-20 10:23:25

@zzz987 先不说 wa 和 re,你 dfs 时间肯定会超,还有,是先 nm,一般使用记忆化搜索。


by zzz987 @ 2024-01-20 10:29:44

n和m确实错了 hh 但是我这个用p数组存搜过的地方不算记忆化吗?


|