玄关求调

P1141 01迷宫

Zmk2009 @ 2024-07-03 21:49:43

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
#define all(s) s.begin(),s.end()
const int M = 1005;
typedef long long ll;
#define endl "\n"
int a[M][M];
queue <pair<int,int> > q;
int dx[] = {0 , 1 , 0 , -1 , 0};
int dy[] = {0 , 0 , 1 , 0 , -1};
int vis[M][M];
int cnt[N];
int n , m;
void BFS(int t){
    cnt[t] ++;
    while (!q.empty()){
        pair <int,int> u = q.front();q.pop();
        for (int i = 1 ; i <= 4 ; i ++){
            int x = u.first + dx[i], y = u.second + dy[i];
            if (x < 1 || x > n || y < 1 || y > m || vis[x][y] || a[u.first][u.second] == a[x][y]) continue;
            vis[x][y] = t;
            q.push(make_pair(x,y));
            cnt[t] ++;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int qu;
    cin >> n >> qu;
    m = n;
    for (int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= m ; j ++){
            char c = getchar();
            while (c != '0' && c != '1') c = getchar();
            a[i][j] = c - '0';
        }
    }
    int tot = 0;
    for (int i = 1 ; i <= n ; i ++){
        for (int j = 1 ; j <= m ; j ++){
            if (!vis[i][j]) {
                q.push(make_pair(i,j));
                vis[i][j] = ++ tot;
                BFS(tot);
            }
        }
    }
    for (int i = 1 ; i <= qu ; i ++){
        int x , y;
        cin >> x >> y;
        cout << cnt[vis[x][y]] << endl;
    }
    return 0;
}

不知道为什么RE + TLE


by FL_sleake @ 2024-07-04 09:40:11

@Zmk2009 读入有问题


by FL_sleake @ 2024-07-04 09:40:53

我把

for (int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= m ; j ++){
            char c = getchar();
            while (c != '0' && c != '1') c = getchar();
            a[i][j] = c - '0';
        }
    }

改成

string a[M];

for (int i = 1 ; i <= n ; i ++){
        cin>>a[i];
        a[i]=" "+a[i];
    }

就过了


by Zmk2009 @ 2024-07-04 16:05:24

@FL_sleake 太感谢了,谢谢巨佬!


|