2021-08-27
（22号学长分享的一道题，今天才来记录。）
我自己的DFS解法（有漏洞）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| 1 #include <bits/stdc++.h>
2 using namespace std;
3 int matrix[30][30];
4 void dfs(int i, int j) {
5 if (matrix[i][j] == 1 || matrix[i][j] == 2) // 是墙，或者走过了，就走人
6 return;
7 if (matrix[i][j] == 0) // 没走过就标记为2
8 matrix[i][j] = 2;
9
10 // 上下左右继续
11 dfs(i, j+1);
12 dfs(i+1, j);
13 dfs(i, j-1);
14 dfs(i-1, j);
15 return;
16 }
17
18 int main() {
19 int n;
20 while (cin >> n) {
21 // 输入，初始化
22 for (int i = 0; i < n; i++)
23 for (int j = 0; j < n; j++)
24 cin >> matrix[i][j];
25
26 for (int i = 0; i < n; i++)
27 for (int j = 0; j < n; j++)
28 if (matrix[i][j] == 1) { // 从左到右，从上到下找到第一个1，然后从它”往右一格往下一格“那一个开始dfs
29 dfs(i+1, j+1);
30
31 // 输出
32 for (int i = 0; i < n; i++) {
33 for (int j = 0; j < n; j++)
34 cout << matrix[i][j] << " ";
35 cout << endl;
36 }
37 return 0;
38 }
39 }
40 }
|
问题在于：第一个2不一定在第一个1的右下也可以在第一个1的正下边（同学提醒我的）。
然后我也尝试了枚举，但是用的方法很蠢很粗暴。总之这道题很简单，解法也多，但是有不少细节需要注意。比如还有一个坑：
我的一次尝试是枚举每一个点，判断从这个点往上下左右方向看都有墙（1）就说明它在墙内（2)。结果三角符号标注的这两个点就被错误地标记为2了。
