TLE90求助

_Liyx_ @ 2024-07-10 11:45:06

#include <bits/stdc++.h>
using namespace std;
int n,m;
string mp[1005];
bool vis[1005][1005];
int x,y;
int ans;
int dx[5]={1,0,-1,0},dy[5]={0,1,0,-1};
struct node{
    int x,y;
};
int aa[100005];
int bb[1005][1005];
void bfs(int id){
    memset(vis,0,sizeof(vis));
    ans=1;
    queue<node> q;
    q.push((node){x,y});
    vis[x][y]=1;
    while(!q.empty()){
        node now=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=now.x+dx[i],yy=now.y+dy[i];
            if(xx>=0&&xx<n&&yy>=0&&yy<n&&vis[xx][yy]==0&&(mp[xx][yy]-'0'+mp[now.x][now.y]-'0')==1){
                vis[xx][yy]=1;
                q.push((node){xx,yy});
                bb[xx][yy]=id;
                ans++;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>mp[i];
    }
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        x--;
        y--;
        if(bb[x][y]!=0){
            cout<<aa[bb[x][y]]<<"\n";
            continue;
        }
        bfs(i);
        aa[i]=ans;
        cout<<ans<<"\n";
    }
    return 0;
}

by wscmh @ 2024-07-10 12:00:28

#include <bits/stdc++.h>

using namespace std;

const size_t MaxN = 1050;
size_t N, M;
string Map[MaxN];
int dx[] = {+1, -1, +0, +0};
int dy[] = {+0, +0, +1, -1};
unsigned int Parent[MaxN * MaxN];
unsigned int Size[MaxN * MaxN];

inline unsigned int Index(const unsigned int &i, const unsigned int &j) {
    return (i - 1) * N + j;
}

unsigned int Find(const unsigned int &v) {
    return Parent[v] == v ? v : Parent[v] = Find(Parent[v]);
}

int main() {
    cin >> N >> M;
    for (size_t i = 1; i <= N; ++i) {
        cin >> Map[i];
        Map[i] = "0" + Map[i];
    }

    for (size_t i = 1; i <= N * N; ++i)
        Parent[i] = i, Size[i] = 1;

    for (size_t i = 1; i <= N; ++i)
        for (size_t j = 1; j <= N; ++j)
            for (size_t k = 0; k != 4; ++k) {
                int a = i + dx[k];
                int b = j + dy[k];
                if (a >= 1 && a <= N && b >= 1 && b <= N)
                    if (Map[i][j] != Map[a][b]) {
                        unsigned int x = Find(Index(i, j));
                        unsigned int y = Find(Index(a, b));
                        if (x != y) {
                            Parent[y] = x;
                            Size[x] += Size[y];
                        }
                    }
            }

    while (M--) {
        int a, b;
        cin >> a >> b;
        cout << Size[Find(Index(a, b))] << endl;
    }

    return 0;
}

by wscmh @ 2024-07-10 12:00:39

@Liyx

by feather20120426 @ 2024-07-10 16:22:02

@Liyx,你的代码可以在算出每一个连通块的大小是多少事，把连通块的每一项赋值成连通块的大小