70分玄关

tangyuanlong @ 2024-06-28 16:26:29

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,qx,qy,b[1010][10010],s;
char a[1010][10010];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,-1,0,1,0};
int dfs(int x,int y)
{
    for(int i=1;i<=4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx>0&&xx<=n&&yy>0&&yy<=n)
        {
            if(a[x][y]=='1'&&a[xx][yy]=='0'&&b[xx][yy]==0)
            {
                b[xx][yy]=1;
                s++;
                dfs(xx,yy);
            }
            else if(a[x][y]=='0'&&a[xx][yy]=='1'&&b[xx][yy]==0)
            {
                b[xx][yy]=1;
                s++;
                dfs(xx,yy);
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    while(m!=0)
    {
        m--;
        memset(b,0,sizeof(b));
        s=1;
        scanf("%d%d",&qx,&qy);
        b[qx][qy]=1;
        dfs(qx,qy);
        printf("%d\n",s);
    }
    return 0;
}

by ATION001 @ 2024-06-28 16:36:33

@tangyuanlong 建议你这么写：

运用连通块的思想，记录一下编号，到时候直接输出

代码：

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
int _x[4]={0,0,-1,1},_y[4]={-1,1,0,0};
int b[1005][1005],sum[100010];
char a[1005][1005];
int n,m;
void bfs(int x,int y,int flag){
    queue<pii>q;
    q.push({x,y});
    sum[flag]++,b[x][y]=flag;
    while(q.size()){
        pii p=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int dx=p.first+_x[i],dy=p.second+_y[i];
            if(a[dx][dy]=='o'||b[dx][dy]!=-1||a[p.first][p.second]==a[dx][dy]){
                continue;
            }
            sum[flag]++,b[dx][dy]=flag;
            q.push({dx,dy});
        }
    }
}
int main(){
    fill(a[0],a[1005],'o');
    fill(b[0],b[1005],-1);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1,x,y;i<=m;i++){
        cin>>x>>y;
        if(b[x][y]==-1){
            bfs(x,y,i);
        }else{
            sum[i]=sum[b[x][y]];
        }
    }
    for(int i=1;i<=m;i++){
        cout<<sum[i]<<endl; 
    }
    return 0;
}

我也TLE过

by tangyuanlong @ 2024-06-28 16:58:13

@ATION001 可以稍微大众化一点吗？（以关）

by ATION001 @ 2024-06-28 23:09:58

@tangyuanlong 通俗一点就是不踩重复的点，这里的连通块的思想其实只是优化。

连通块的思想这里运用的是先预处理，把图跑一遍，在一个连通块内的点能走的点个数都相同，最后直接输出即可

by tangyuanlong @ 2024-07-01 07:52:30

@ATION001 谢谢