P1141 01迷宫题解

柔光的暖阳◎ 2022-05-14 14:08 133阅读 0赞

这道题我一共写了22遍，最后AC的时候手都在颤抖，，，

先说一下思路，洛谷有大佬用并查集，等等各种高端操作。虽然我也用并查集写了，但是效果不是太理想。

我的思路是G\[ \]\[ \]存放图，V\[ \]\[ \]并不是存放图状态，V\[ \] \[ \]存放这是第几个连通图，再用一个数组a\[ \] 来存放每个联通图的元素数量，配合经典宽度搜索，得出答案。

#include<cstdio>
    #include<cstdlib>
    #include<iostream>
    using namespace std;
    int n,m,G[1010][1010],x,y,maxv=0,f[1010][1010];//f就是大家经常用的v状态数组，只不过这里存放联通图编号。 
    int num=1,a[1000010],next[4][2]={
       {0,1},{0,-1},{1,0},{-1,0}};//num是每个连通图独有的编号，从1开始。a[]是存放每个图的个数（a[num]）.
    void bfs(int x,int y){
        int x1,y1;
        for(int i=0;i<4;i++){
            x1=x+next[i][0];
            y1=y+next[i][1];
            if(1<=x1&&x1<=n&&1<=y1&&y1<=n&&!f[x1][y1]&&(G[x1][y1]!=G[x][y])){
                f[x1][y1]=num;
                maxv++;
                bfs(x1,y1);
            }
        }
    }//经典广度搜索，每次搜索都会得出一个maxv元素个数
    int main(){
        int x1,y1;
        cin>>n>>m;
        char c[1100];
        for(int i=1;i<=n;i++){
            scanf("%s",c);
            for(int j=1;j<=n;j++)
                if(c[j-1]=='1')G[i][j]=1;
        }//输入图
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(!f[i][j]){//如果这个点没有在任何图中
                    num++;//编号加1
                    maxv=1;//初始化最大元素数
                    f[i][j]=num;
                    bfs(i,j);
                    a[num]=maxv;//存放图的元素个数
                } 
            }    
          while(m--){
            cin>>x1>>y1;
            cout<<a[f[x1][y1]]<<endl;    //输出
        }
    }