Little_x_starTYJ @ 2024-09-05 11:15:20

#include <bits/stdc++.h>
using namespace std;
int n, m;
bool vis[1010][1010];
char c[1010][1010];
int a[1010][1010];
struct node {
    int x, y;
};
queue<node> q;
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};
inline int bfs(int x, int y) {
    int res = 1;
    q.push({x, y});
    vis[x][y] = 1;
    while(!q.empty()) {
        node t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = t.x + dx[i];
            int yy = t.y + dy[i];
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && (c[xx][yy] == '0' && c[t.x][t.y] == '1' || c[xx][yy] == '1' && c[t.x][t.y] == '0') && !vis[xx][yy]) {
                q.push({xx, yy});
                res++;
                vis[xx][yy] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (vis[i][j])
                a[i][j] = res;
            vis[i][j] = false;
        }
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> c[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!a[i][j])
                a[i][j] = bfs(i, j);
    while (m--) {
        int x, y;
        cin >> x >> y;
        cout << a[x][y] << "\n";
    }
}

by Hhy140516 @ 2024-09-05 11:21:39

首先先看我的

#include<bits/stdc++.h>
using namespace std ;
int vis[1005][1005] ;
bool f[1005][1005] ;
int t[1000005] ;
int cx[] = {1 , -1 , 0 , 0} , cy[] = {0 , 0 , 1 , -1} ;
int n , m ;
int cnt ;
void dfs(int x , int y)
{
    if(x < 1 || y < 1 || x > n || y > n || vis[x][y]) return ;
    vis[x][y] = cnt ;
    for( int i = 0 ; i < 4 ; i++ )
    {
        int nx = x + cx[i] , ny = y + cy[i] ;
        if(f[x][y] == !f[nx][ny])
        {
            dfs(nx , ny) ;
        }
    }
}
signed main()
{
    cin >> n >> m ;
    for( int i = 1 ; i <= n ; i++ ) 
    {
        for( int j = 1 ; j <= n ; j++ ) scanf("%01d" , &f[i][j]) ;
    }
    for( int i = 1 ; i <= n ; i++ )
    {
        for( int j = 1 ; j <= n ; j++ )
        {
            if(vis[i][j] == 0)
            {
                cnt++ ;
                dfs(i , j) ;
            }
        }
    }
    for( int i = 1 ; i <= n ; i++ )
    {
        for( int j = 1 ; j <= n ; j++ ) t[vis[i][j]]++ ;
    }
    while(m--)
    {
        int l , r ;
        cin >> l >> r ;
        cout << t[vis[l][r]] << "\n" ;
    }
    return 0 ;
}

by Hagasei @ 2024-09-05 11:34:56

复杂度有问题。注意到同一个连通块里的答案是一样的，所以一个连通块只需要跑一次（即不清空 vis 标记），然后把整个连通块的答案都记上。

by Hhy140516 @ 2024-09-05 11:37:56

#include <bits/stdc++.h>
using namespace std;
int n, m;
bool vis[1010][1010];
char c[1010][1010];
int a[1010][1010];
struct node {
    int x, y;
};
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};
void bfs(int x, int y) {
    memset(vis , 0 , sizeof vis) ;
    queue<node> q;
    int res = 1;
    q.push({x, y});
    vis[x][y] = 1;
    while(!q.empty()) {
        node t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = t.x + dx[i];
            int yy = t.y + dy[i];
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && ((c[xx][yy] == '0' && c[t.x][t.y] == '1') || (c[xx][yy] == '1' && c[t.x][t.y] == '0')) && !vis[xx][yy]) {
                q.push({xx, yy});
                res++;
                vis[xx][yy] = 1;
            }
        }
    }
    memset(vis , 0 , sizeof vis) ;
    q.push({x, y});
    vis[x][y] = 1;
    a[x][y] = res ;
    while(!q.empty()) {
        node t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = t.x + dx[i];
            int yy = t.y + dy[i];
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && ((c[xx][yy] == '0' && c[t.x][t.y] == '1') || (c[xx][yy] == '1' && c[t.x][t.y] == '0')) && !vis[xx][yy]) {
                q.push({xx, yy});
                a[xx][yy] = res ;
                vis[xx][yy] = 1;
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> c[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!a[i][j])
                bfs(i, j);
    while (m--) {
        int x, y;
        cin >> x >> y;
        cout << a[x][y] << "\n";
    }
}

自己改 dfs 吧

by Hhy140516 @ 2024-09-05 11:43:54

但是我感觉我这个代码能过的啊

时间复杂度是 O(n+m) 的

by Hhy140516 @ 2024-09-05 11:46:41

我知道了，因为 vis 数组每次要清空，如果全是 0 或 1 的话，时间复杂度有可能会有 O(1000000n) ，所以会有两个点不过

by Little_x_starTYJ @ 2024-09-06 10:12:38

@Hhy140516 @Hagasei thx，已解决，已关。

by Hhy140516 @ 2024-09-06 10:18:03

@IOI_ILJYT 已互关