题面(from luogu) 01迷宫 有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格11上，同样若你位于一格1上，那么你可以移动到相邻44格中的某一格0上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入格式： 第1行为两个正整数n,m 下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。
接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。
输出格式： m行，对于每个询问输出相应答案。
输入样例#1： 2 2 01 10 1 1 2 2 输出样例#1： 4 4 所有格子互相可达。 对于20%的数据，n≤10； 对于40%的数据，n≤50； 对于50%的数据，m≤5； 对于60%的数据，n≤100,m≤100； 对于100%的数据，n≤1000,m≤100000。
题目分析① 看到这一题的第一个思路，就是暴力DFS，直接上去写，读进来一组，就做一遍联通块，可以直接套模板
代码（70暴力DFS联通块）
#include <bits/stdc++.h> using namespace std; int dx[5]={0,-1,0,0,1}; //4各方向的介值 int dy[5]={0,0,1,-1,0}; int vis[1009][1009],a[1009][1009],n,m,max1,total,ans[10000],u,v; //vis判断是否会重复走 char ch; void search(int x,int y) //x，y是搜到哪里了 { if (x > n || x < 1 || y > n || y < 1) //判断是否走出地图 return; else //反之，这就是一个可行走法 { total++; //加上这个联通块 for (int i = 1; i <= 4; i++) //向4个方向走 { if (vis[x+dx[i]][y+dy[i]] != 1 && a[x+dx[i]][y+dy[i]] != a[x][y]) //判断下一个格子是否合法（①没走过 ②符合题意） { vis[x+dx[i]][y+dy[i]] = 1; //打标记 search(x+dx[i],y+dy[i]); //向前走 // vis[x+dx[i]][y+dy[i]] = 0; //不用回溯，因为一个格子只可以走一次 } } } } int main() { //初始化 memset(vis,0,sizeof(vis)); memset(ans,0,sizeof(ans)); //输入 cin>>n>>m; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { cin>>ch; if (ch == '1') a[i][j] = 1; //对图的转换 else a[i][j] = 0; } for (int t = 1; t <= m; t++) { memset(vis,0,sizeof(vis)); //做一次就清一次0，符合边读边做的思想 cin>>u>>v; //输入起点 total = 0; //当前没有联通块 vis[u][v] = 1; //标示起点走过，不重复走了 search(u,v); //开始搜 ans[t] = total; //存答案 } for (int i = 1; i <= m; i++) cout<<ans[i]<<endl; //输出 return 0; }题目分析② 从上面的思路来看，超时是不可避免的，所以只能去写那个算法了——MS（记忆化搜索）
顾名思义，MS与DP类似（可以说是低配版的DP），大多是情况下是判断当前的走法走到当前的格子哪里，是否是比当前最优走法走到的更优， 在这里，我们是用来判断当前点是否走过了，以联通块的思想来看，一次走过的所有格子，他们能到达的联通块的个数是一样的，所以我们就很好解决了MS的存储问题
但是，我们还有一个问题要解决： 怎么判断一条路径上的点都走过呢？也就是怎么判断这个点是否已经有了值呢？ 是直接的两重循环把在搜索过程中走过的也就是打了标记的全部赋值吗？ 这个是明显超时的 所以我们得去想一个更优的方案
一条路上，他们的值都是一样的，那么我们为什么不能特指一下这条路径上一条途径的点呢？ 也就是把找到的值赋给那个特定的点（后面都是一样的），标记一下这条路上的所有点都经过那一个特定的点不就行了吗？ 但是，你们不觉得这很像并查集的思想吗？ 我们可以把这一条路径的起点当做那一个特定的点，这一条路径上所有的点都指向那一个起点，这一条路径上都是起点的值~~（用人话讲）~~ 专业一点说就是:我们把一条路上走过的所有点都指向他的起始点，也就是根节点，一条树上的值都是一样的 所以在判断时我们只要判断它指向的根节点的位置位置上是否有值就行了
代码（完美的 MS+并查集 ）
#include <bits/stdc++.h> using namespace std; int dx[4]={0,-1,0,1}; int dy[4]={-1,0,1,0}; int a[1009][1009],genx[1009][1009],geny[1009][1009],ans[1009][1009]; //genx,geny是用来存储当前点的根坐标的（genx是当前x节点的根的x坐标，geny同理） bool vis[1009][1009]; int sum,n,m,start_x,start_y; void search(int x,int y) { if (x < 1 || x > n || y < 1 || y > n || vis[x][y]) return; //边界，不重复走，不走出去 if (ans[x][y] > 0) return; //记忆化：当前点走过了，就不找了 //反之 sum++; //当前找到了一个联通块 vis[x][y] = true; //打标记 //对根节点的指向 genx[x][y] = start_x; geny[x][y] = start_y; for (int i = 0; i < 4; i++) //4个方向向前走 if (a[x+dx[i]][y+dy[i]] != a[x][y]) search(x+dx[i],y+dy[i]); } int main() { //初始化 memset(ans,0,sizeof(ans)); memset(genx,0,sizeof(genx)); memset(geny,0,sizeof(geny)); memset(a,0,sizeof(a)); memset(vis,false,sizeof(vis)); cin>>n>>m; //输入 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { char c; cin>>c; a[i][j] = c - '0'; //强制类型转换 } for (int k = 1; k <= m; k++) { cin>>start_x>>start_y; //读入当前起始点的坐标 if (ans[genx[start_x][start_y]][geny[start_x][start_y]] > 0) //判断有没有走过 { cout<<ans[genx[start_x][start_y]][geny[start_x][start_y]]<<endl; continue; } //反之就是没有走过 sum = 0; search(start_x,start_y); //得搜一遍 ans[start_x][start_y] = sum; //记忆化 //自己指向自己，防止重复的数据 genx[start_x][start_y] = start_x; geny[start_x][start_y] = start_y; cout<<sum<<endl; //输出 } return 0; //完美的结束程序 } **菜鸡c_uizrp_dzjopkl原创**