冈布奥组合2019，2019.1.23 01迷宫

题目传送门

不难发现因为格子能走的判定是双向的

所以所有连在一起的格子能走到的格子个数都是一样的

冈布奥组合2019？也就是说只要知道了一个格子能走到多少格子这些能走到的格子的解都可以求出来

于是我们想到了并查集

对于二维的并查集可以使用映射的方法

也就是将（i，j）映射到i*n+j

7本迷宫阵、代码

 

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,p,q;
char map[1050][1050];
int fa[1050][1050],book[150000000];
int fi(int p,int q)//查找函数
{if(fa[p][q]==p*10000+q)return p*10000+q;return fa[p][q]=fi(fa[p][q]/10000,fa[p][q]%10000);//路径压缩，注意fi函数里的参数是逆映射
}
void u(int p1,int q1,int p2,int q2)//合并函数
{if(fi(p1,q1)!=fi(p2,q2)){if(fa[p2][q2]>fa[p1][q1])fa[fi(p2,q2)/10000][fi(p2,q2)%10000]=fa[fi(p1,q1)/10000][fi(p1,q1)%10000];else fa[fi(p1,q1)/10000][fi(p1,q1)%10000]=fa[fi(p2,q2)/10000][fi(p2,q2)%10000];}//特别注意合并祖先的时候合并的是两个节点父亲的祖先，因为路径压缩再加上合并之后的树是三层的树return;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>map[i][j];fa[i][j]=i*10000+j;}getchar();}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(j<n&&(int(map[i][j]-48))^(int(map[i][j+1]-48))==1)u(i,j,i,j+1);if(i<n&&(int(map[i][j]-48))^(int(map[i+1][j]-48))==1)u(i,j,i+1,j);}//每次搜索向右、向下，若可以走则合并
    }for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){++book[fi(i,j)];fa[i][j]=fi(i,j);}}for(int i=1;i<=m;i++){scanf("%d%d",&p,&q);printf("%d\n",book[fa[p][q]]);}return 0;
}