洛谷 P1141 01迷宫题解
题目链接：https://www.luogu.org/problem/p1141
题目描述
有一个仅由数字00与11组成的n \times nn×n格迷宫。若你位于一格0上，那么你可以移动到相邻44格中的某一格11上，同样若你位于一格1上，那么你可以移动到相邻44格中的某一格00上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入格式
第11行为两个正整数n,mn,m。
下面nn行，每行nn个字符，字符只可能是00或者11，字符之间没有空格。
接下来mm行，每行22个用空格分隔的正整数i,ji,j，对应了迷宫中第ii行第jj列的一个格子，询问从这一格开始能移动到多少格。
输出格式
mm行，对于每个询问输出相应答案。
输入输出样例
2 2 01 10 1 1 2 2
4 4
说明/提示
所有格子互相可达。
对于20\%20%的数据，n≤10n≤10；
对于40\%40%的数据，n≤50n≤50；
对于50\%50%的数据，m≤5m≤5；
对于60\%60%的数据，n≤100,m≤100n≤100,m≤100；
对于100\%100%的数据，n≤1000,m≤100000n≤1000,m≤100000。
题解
先介绍采用裸的bfs，当然不能满分。再介绍如何优化得到满分。
1 #include <iostream>
2 #include <stdio.h>
3 #include <math.h>
4 #include <algorithm>
5 #include <string.h>
6
7 using namespace std;
8
9 struct node
10 {
11 int x, y;
12 };
13 node q[1000005];
14
15 const int maxn = 1005;
16 int n, m, a, b, c, d, front, last, step;
17 int pos[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
18 char abc[maxn][maxn]; // 存储输入的矩阵信息
19 bool vis[maxn][maxn]; // 是否已经遍历过该点
20
21
22 void bfs()
23 {
24 node now;
25 now.x = a;
26 now.y = b;
27 vis[a][b] = 1;
28
29 front = last = 0;
30 q[last] = now;
31 last++;
32 while(front < last)
33 {
34 now = q[front++];
35 for(int i = 0; i < 4; i++)
36 {
37 int nx = now.x + pos[i][0];
38 int ny = now.y + pos[i][1];
39 if(nx <= n && nx > 0 && ny <= n && ny > 0
40 && vis[nx][ny] == false
41 && abc[now.x][now.y] != abc[nx][ny])
42 {
43 vis[nx][ny] = true;
44 q[last].x = nx;
45 q[last].y = ny;
46 step++;
47 last++;
48 }
49 }
50 }
51 }
52
53 int main()
54 {
55 cin >> n >> m;
56 for(int i = 1; i <= n; i++)
57 {
58 for(int j = 1; j <= n; j++)
59 {
60 cin >> abc[i][j];
61 }
62 }
63 for(int i = 1; i <= m; i++)
64 {
65 cin >> a >> b;
66 step = 1;
67 bfs();
68 cout << step << endl;
69 memset(vis, 0, sizeof(vis));
70 }
71 return 0;
72 }
裸的bfs并没有什么技巧，只是注意q队列不要太小，太小会导致wa。这个代码会有3个测试点tle。
之所以会出现tle，主要是有很多次询问，每次询问都做了一次bfs，要优化代码就要减少bfs的次数。注意到这样一个事实：如果迷宫中存在连通块，则连通块中各格子到其他格子的个数是相同的。而求连通块本身就是利用bfs实现的。下面就是利用连通块进行优化的代码。
1 #include <iostream>
2 #include <stdio.h>
3 #include <math.h>
4 #include <algorithm>
5 #include <string.h>
6
7 using namespace std;
8
9 struct node
10 {
11 int x, y;
12 };
13 node q[1000005];
14 int cnt[1000005];
15
16 const int maxn = 1005;
17 int n, m, a, b, c, d, front, last, step, num;
18 int pos[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
19 char abc[maxn][maxn]; // 存储输入的矩阵信息
20 bool vis[maxn][maxn]; // 是否已经遍历过该点
21 int map[maxn][maxn]; // 用于对连通块染色
22
23
24 void bfs()
25 {
26 node now, next;
27 now.x = a;
28 now.y = b;
29 map[a][b] = num;
30 vis[a][b] = 1;
31 step = 1;
32
33 front = last = 0;
34 q[last] = now;
35 last++;
36 while(front < last)
37 {
38 now = q[front++];
39 for(int i = 0; i < 4; i++)
40 {
41 int nx = now.x + pos[i][0];
42 int ny = now.y + pos[i][1];
43 if(nx <= n && nx > 0 && ny <= n && ny > 0
44 && vis[nx][ny] == false
45 && abc[now.x][now.y] != abc[nx][ny])
46 {
47 vis[nx][ny] = true;
48 q[last].x = nx;
49 q[last].y = ny;
50 map[nx][ny] = num;
51 step++;
52 last++;
53 }
54 }
55 }
56 cnt[num] = step;
57 num++;
58 }
59
60 int main()
61 {
62 cin >> n >> m;
63 for(int i = 1; i <= n; i++)
64 {
65 for(int j = 1; j <= n; j++)
66 {
67 cin >> abc[i][j];
68 }
69 }
70 num = 1;
71 for(int i = 1; i <= m; i++)
72 {
73 cin >> a >> b;
74 if(map[a][b] == 0)
75 {
76 bfs();
77 }
78 cout << cnt[map[a][b]] << endl;
79 }
80 return 0;
81 }
其中的map数组是用来存储连通块的染色信息的。如果格子对应的map数据为0，说明没有做过bfs。cnt数组存储着每个连通块所对应的格子个数。经过这次优化，就可以ac了。