题目描述
有一个仅由数字0与11组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入格式：
第1行为两个正整数n,m。
下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。
接下来mm行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。
输出格式：
输入样例#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。
题目分析
很普通的bfs题，但是注意到她的数据规模很大，要适当的优化。
分析题过后，我们可以发现，迷宫当中可以互相到达的点，能够组成一个集合，且集合中的点能移动几个格子的个数都是相等的，
另外，在输入矩阵时，数字之间没有空格，我们需要用scanf(“%1d”, &maze[i][j])来读取。
#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, &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; }