再次求调

Walledjc @ 2024-08-11 10:49:37

#include<bits/stdc++.h> 
using namespace std;
long long n,m,vis[1005][1005],mp[1005][1005],ans[1005][1005],cnt=1,tmp;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int sx,int sy,int tmp){
    vis[sx][sy]=1;
    for(int i=0;i<4;i++){
        int tx=sx+dx[i];
        int ty=sy+dy[i];
        if(tx<1||ty<1||tx>n||ty>n||vis[tx][ty]==1) continue;
        if(tmp==0&&mp[tx][ty]==0) continue;
        if(tmp==1&&mp[tx][ty]==1) continue;
        vis[tx][ty]=1;
        cnt++;
        dfs(tx,ty,!tmp);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char ch;
            cin>>ch;
            mp[i][j]=ch-'0';
        }
    } 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[i][j]==0){
                dfs(i,j,mp[i][j]);
                ans[i][j]=cnt;
                cnt=1;
                memset(vis,0,sizeof(vis));
            }
        }
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        cout<<ans[a][b]<<endl;
    }
    return 0;
}

by _zhang @ 2024-08-11 11:05:51

@Walledjc 这题用广搜。。。（深搜广搜不是乱用的

by Walledjc @ 2024-08-11 11:12:16

@_zhang 广搜我4WA7TLE ，深搜起码40分

by _zhang @ 2024-08-11 11:14:03

em，肯定是你的广搜代码有问题

by 违规用户名Jx9)zIu @ 2024-08-11 11:14:10

完全脱离正常解法

by _zhang @ 2024-08-11 11:16:05

好像能用dfs解决 @Walledjc 我找一下刚才写的代码

by _zhang @ 2024-08-11 11:17:18

#include <cstdio>
#include <cstring>
int n, m, ans[100005], x, y, f[1005][1005];
char s[1005][1005];
void dfs(int r, int c, int z, int i) {
    if (r < 0 || r >= n || c < 0 || c >= n || f[r][c] != -1 || s[r][c] - '0' != z) return;
    f[r][c] = i, ans[i]++;
    dfs(r - 1, c, !z, i);
    dfs(r + 1, c, !z, i);
    dfs(r, c - 1, !z, i);
    dfs(r, c + 1, !z, i);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%s", s[i]);
    memset(f, -1, sizeof(f));
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &x, &y);
        x--, y--;
        if (f[x][y] == -1) dfs(x, y, s[x][y] - '0', i);
        else ans[i] = ans[f[x][y]];
    }
    for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
    return 0;
}

by _zhang @ 2024-08-11 11:19:08

f[i][j]是调试用的，写的时候其实用bool数组即可

by Walledjc @ 2024-08-11 11:37:17

@_zhang 我的理想状态是直接把每一个连通图的成员在

by _zhang @ 2024-08-11 12:25:30

@Walledjc 大概理解你的意思了，其实你可以把一个联通块的点在dfs的过程中存到vector<pair<int,int>>里，最后把vector中所有点的ans更新，最后clear一下vector（虽然可行但已经有些累赘了

by _zhang @ 2024-08-11 12:34:52

@Walledjc 收回我前一句话，f[i][j]的数值是有用的