玄关，bfs并查集WA求调

GB2312 @ 2024-09-23 21:21:12

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,i,j,k,nowx,nowy;
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
bool a[N][N],vis[N][N];
char s;
struct point
{
    int x,y;
    friend bool operator ==(point p,point q)
    {
        return (p.x==q.x&&p.y==q.y);
    }
    friend bool operator <(point p,point q)
    {
        return p.x<q.x;
    }
}now,tmp,vising;
map<point,point> fa;
map<point,int> cnt;
queue<point> q;
point find(point p)
{
    if(p==fa[p]) return p;
    return fa[p]=find(fa[p]);
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin>>s;
            a[i][j]=(s-'0');
            tmp.x=i,tmp.y=j;
            fa[tmp]=tmp;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(!vis[i][j])
            {
                vising.x=i,vising.y=j;
                q.push(vising);
                while(!q.empty())
                {
                    now=q.front();q.pop();
                    nowx=now.x,nowy=now.y;
                    fa[now]=vising;
                    if(!vis[nowx][nowy])
                    {
                        vis[nowx][nowy]=1;
                        for(k=0;k<4;k++)
                        {
                            tmp.x=nowx+fx[k],tmp.y=nowy+fy[k];
                            if(tmp.x>0&&tmp.x<=n&&tmp.y>0&&tmp.y<=n) q.push(tmp);
                        }
                    }
                }
            }
        }
    }
    for(i=1;i<=n;i++) 
    {
        for(j=1;j<=n;j++)
        {
            tmp.x=i,tmp.y=j;
            tmp=find(tmp);
            cnt[tmp]++;
        }
    }
    while(m--)
    {
        cin>>i>>j;
        tmp.x=i,tmp.y=j;
        tmp=find(tmp);
        cout<<cnt[tmp]<<'\n';
    }
    return 0;
}

by naijgnorgnahz @ 2024-09-23 21:34:00

@GB2312 请问你a数组读入后在哪用到了呢？

by GB2312 @ 2024-09-23 21:41:11

@naijgnorgnahz 哦哦我知道了 谢谢

by GB2312 @ 2024-09-23 21:43:41

@naijgnorgnahz 但是还是WA啊

by GB2312 @ 2024-09-23 21:44:09

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,i,j,k,nowx,nowy;
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
bool a[N][N],vis[N][N];
char s;
struct point
{
    int x,y;
    friend bool operator ==(point p,point q)
    {
        return (p.x==q.x&&p.y==q.y);
    }
    friend bool operator <(point p,point q)
    {
        return p.x<q.x;
    }
}now,tmp,vising;
map<point,point> fa;
map<point,int> cnt;
queue<point> q;
point find(point p)
{
    if(p==fa[p]) return p;
    return fa[p]=find(fa[p]);
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin>>s;
            a[i][j]=(s-'0');
            tmp.x=i,tmp.y=j;
            fa[tmp]=tmp;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(!vis[i][j])
            {
                vising.x=i,vising.y=j;
                q.push(vising);
                while(!q.empty())
                {
                    now=q.front();q.pop();
                    nowx=now.x,nowy=now.y;
                    fa[now]=vising;
                    if(!vis[nowx][nowy])
                    {
                        vis[nowx][nowy]=1;
                        for(k=0;k<4;k++)
                        {
                            tmp.x=nowx+fx[k],tmp.y=nowy+fy[k];
                            if(tmp.x>0&&tmp.x<=n&&tmp.y>0&&tmp.y<=n&&(a[nowx][nowy]^a[tmp.x][tmp.y])) q.push(tmp);
                        }
                    }
                }
            }
        }
    }
    for(i=1;i<=n;i++) 
    {
        for(j=1;j<=n;j++)
        {
            tmp.x=i,tmp.y=j;
            tmp=find(tmp);
            cnt[tmp]++;
        }
    }
    while(m--)
    {
        cin>>i>>j;
        tmp.x=i,tmp.y=j;
        tmp=find(tmp);
        cout<<cnt[tmp]<<'\n';
    }
    return 0;
}

@naijgnorgnahz

by GB2312 @ 2024-09-23 21:44:54

@naijgnorgnahz 评测记录

by naijgnorgnahz @ 2024-09-23 21:51:24

@GB2312 没道理啊

by naijgnorgnahz @ 2024-09-23 21:52:06

@GB2312 会不会map挂了

by naijgnorgnahz @ 2024-09-23 21:52:32

你那个结构体比大小

by GB2312 @ 2024-09-23 21:53:11

@naijgnorgnahz 结构体比大小就是应付下map要求

by naijgnorgnahz @ 2024-09-23 21:54:21

我理解如果两个point的x相同而y不相同，那么两个point互相不小于对方，就会在stl里被认为相等

@GB2312