80,WA 3 和 11,求debug

P1141 01迷宫

luoguerepp @ 2024-03-07 19:15:26

#include<iostream>
#include<queue>

using namespace std;

const int N = 1010;
typedef pair<int,int> PII; 

int n,m;
char g[N][N];
bool st[N][N];
int group[N][N],id;
int sum[N];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

void bfs(int x0,int y0){
    queue<PII> q;
    q.push({x0,y0});
    st[x0][y0] = true;
    group[x0][y0] = id;

    int cnt = 1;
    while(q.size()){
        auto t = q.front();
        q.pop();

        int x = t.first,y = t.second;
        for(int i = 0; i < 4; ++i){
            int a = x + dx[i],b = y + dy[i];
            if(a >= 1 && a <= n && b >= 1 && b <= n){
                if(st[a][b] || g[a][b] == g[x][y])  continue;
                st[a][b] = true;
                group[a][b] = id;
                cnt++;
                q.push({a,b});
            }
        }
    }

    sum[id++] = cnt;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; ++i) scanf("%s",g[i] + 1);

    // for(int i = 1; i <= n; ++i)
    //     for(int j = 1; j <= n; ++j)
    //         if(!st[i][j])   bfs(i,j);

    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        if(!st[a][b])   bfs(a,b);
        printf("%d\n",sum[group[a][b]]);
    }

    return 0;
}

by luoguerepp @ 2024-03-07 19:16:16

group是给每个连通块分组的


by luoguerepp @ 2024-03-09 21:37:12

破案了,记录每个连通块个数的数组sum[]开太小了


|