悬关，求助

huyangmu @ 2023-12-09 22:29:08

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int NR = 1e3 + 5;
int n,m,x,y,a[NR][NR],vis[NR][NR],ans[NR],sum,cnt;
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
struct node{
    int x,y;
};
void bfs (int x,int y){
    cnt=1;
    queue<node>q;
    q.push(node{x,y});
    vis[x][y]=sum;
    while (!q.empty()){
        node tmp=q.front();q.pop();
        for (int i=0;i<4;++i){
            int u=tmp.x+dx[i],v=tmp.y+dy[i];
            if (u<1||u>n||v<1||v>n||vis[u][v]||a[u][v]==a[tmp.x][tmp.y]) continue;
            vis[u][v]=sum;
            ++cnt;
            q.push(node{u,v});
        }
    }
}
signed main (){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            char x;
            cin>>x;
            a[i][j]=x-'0';
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            if (vis[i][j]==0){
                ++sum;
                bfs(i,j);
                ans[sum]=cnt;               
            }
        }
    }
    for (int i=1;i<=m;++i){
        cin>>x>>y;
        cout<<ans[vis[x][y]]<<'\n';
    }
    return 0;
}

by Manchester_Is_Blue @ 2023-12-09 22:34:53

错哪了？

by cyj0314 @ 2023-12-09 22:52:21

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int NR = 1e3 + 5;
int n,m,x,y,a[NR][NR],vis[NR][NR],ans[NR],sum,cnt;
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
struct node{
    int x,y;
};
void bfs (int x,int y){
    cnt=1;
    queue<node>q;
    q.push(node{x,y});
    vis[x][y]=sum;
    while (!q.empty()){
        node tmp=q.front();q.pop();
        for (int i=0;i<4;++i){
            int u=tmp.x+dx[i],v=tmp.y+dy[i];
            if (u<1||u>n||v<1||v>n||vis[u][v]==sum||a[u][v]==a[tmp.x][tmp.y]) continue;
            vis[u][v]=sum;
            ++cnt;
            q.push(node{u,v});
        }
    }
}
signed main (){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            char x;
            cin>>x;
            a[i][j]=x-'0';
        }
    }
    for (int i=1;i<=m;++i){
        cin>>x>>y;
        ++sum;
        bfs(x,y);       
        cout<<cnt<<'\n';
    }
    return 0;
}

这样有八十分有三个TLE 试一下用四个if代替循环，会快一点

by huyangmu @ 2023-12-11 22:56:29

%%% 但我们好像壶关了@cyj0314

by cyj0314 @ 2023-12-12 09:21:29

有吗

by cyj0314 @ 2023-12-12 09:22:17

也行吧，可能我关过没注意吧

by jmy20120722 @ 2024-01-13 10:20:51

火钳刘明