首页 > > 程序设计 > C/C++ >

洛谷 P1141 01迷宫题解

2019-08-16 08:00:03来源：博客园阅读 ()

洛谷 P1141 01迷宫题解

题目链接：https://www.luogu.org/problem/P1141

题目描述

有一个仅由数字 $\times nn×n格迷宫。若你位于一格0上，那么你可以移动到相邻44格中的某一格11上，同样若你位于一格1上，那么你可以移动到相邻44格中的某一格00上。$

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入格式

第

下面

接下来

输出格式

输入输出样例

输入 #1

输出 #1

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 }