输入样例#1：
2 2
01
10
1 1
2 2
输出样例#1：
4
4
所有格子互相可达。
对于20%的数据，n≤10n≤10；
对于40%的数据，n≤50n≤50；
对于50%的数据，m≤5m≤5；
对于60%的数据，n≤100,m≤100n≤100,m≤100；
对于100%的数据，n≤1000,m≤100000n≤1000,m≤100000。
#include <iostream> #include <stdio.h> #include <algorithm> #include <queue> #include <string> #include <map> using namespace std; struct node { int x, y; node(int a, int b) { x = a; y = b; } }; int n, m; int maze[1000 + 2][1000 + 2]; int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; int p_sum[1000 + 2][1000 + 2];//标记第i行j列的点，在哪个集合中 int set[100000 + 2];//第i个集合中的点能走几步 bool check(int x, int y) { if (x < 0 || y < 0 || y >= n || x >= n) return false; return true; } int bfs(int index,int a, int b) { int sum = 0; queue<node> myq; myq.push(node(a, b)); while (!myq.empty()) { //出队 int x = myq.front().x; int y = myq.front().y; myq.pop(); //若已在集合中，则跳过 if (p_sum[x][y] != 0) continue; //将点加入集合 p_sum[x][y] = index; sum++; //枚举所有方向 for (int i = 0; i < 4; i++) { int xx = x + dir[i][0]; int yy = y + dir[i][1]; if (check(xx, yy) && maze[x][y] != maze[xx][yy]) myq.push(node(xx, yy)); } } set[index] = sum; return sum; } int main(){ scanf("%d %d\n", &n, &m); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%1d", &maze[i][j]); } } for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); if (p_sum[a - 1][b - 1]) cout << set[p_sum[a - 1][b - 1]] << endl; else cout << bfs(i + 1, a - 1, b - 1) << endl; } return 0; }
原文：https://www.cnblogs.com/woxiaosade/p/10654238.html