题目描述
有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格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
思路： 本体就是BFS的模板题，有一点应该注意到就是连通的格子之间的答案是一样的，即求连通分量。在这里我们用fx[maxn][maxn]数组和fy[maxn][maxn]数组记录该格子的祖父（fx,fy），即该格子是从（fx,fy）通过BFS扩展来的，类似于并查集。ans[maxn][maxn]数组记录格子的答案。 住：这里要注意读入的问题，将在另一篇博客提到。 代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<string> #include<map> using namespace std; int n, m; const int maxn = 1005; char mp[maxn][maxn]; int ans[maxn][maxn]; int dir[4][2] = { {1,0},{-1,0}, {0,1}, {0,-1} }; int vis[maxn][maxn]; int fx[maxn][maxn]; int fy[maxn][maxn]; struct p { int x, y; p(int xx, int yy) { x = xx; y = yy; } }; void bfs(int x, int y) { int cnt = 1; //题目里说明每个格子自己是可达的 queue<p>q; q.push(p(x, y)); vis[x][y] = 1; while (!q.empty()) { p f = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int xx = f.x+dir[i][0]; int yy = f.y +dir[i][1]; if (xx > 0 && xx <=n&&yy > 0 && yy <= n&&!vis[xx][yy]) { if (mp[f.x][f.y] != mp[xx][yy]) { //0只能到1,1只能到0 q.push(p(xx, yy)); fx[xx][yy] = x; //记录祖父的x坐标与y坐标 fy[xx][yy] = y; vis[xx][yy] = 1; cnt++; } } } } ans[x][y] = cnt; //x，y确定的格子可达的格子数 } int main() { memset(ans, 0, sizeof ans); memset(vis, 0, sizeof vis); memset(fx, 0, sizeof fx); memset(fy, 0, sizeof fy); scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%s", mp[i] + 1); } for (int i = 1; i < m; i++) { int x, y; scanf("%d %d", &x, &y); if (ans[x][y]) printf("%d\n", ans[x][y]); else { if (fx[x][y]) ans[x][y] = ans[fx[x][y]][fy[x][y]]; else bfs(x, y); printf("%d\n", ans[x][y]); } } int x, y; scanf("%d %d", &x, &y); if (ans[x][y]) //如果已经求得答案，直接输出 printf("%d", ans[x][y]); else { if (fx[x][y]) //如果该点是由其他节点扩展来的，因为在同一个连通分量里，所以答案跟祖父节点的答案相同 ans[x][y] = ans[fx[x][y]][fy[x][y]]; else //如果该点还没有被扩展，BFS bfs(x, y); printf("%d", ans[x][y]); } return 0; }