题目

有一张 n*m 的棋盘，每个位置上有一颗棋子 X 或 O。若一块区域的 O 被 X 四周包围，那么这些 O 会变成 X，除了边界上的 O。

给定一张棋盘和初始状态的棋子，输出变化后的棋盘。

示例

输入：
X X X X X
X O O X X
X X O X X
X X X O X
X O X O X
输出：
X X X X X
X X X X X
X X X X X
X X X O X
X O X O X

思路

岛屿问题，先写个 dfs 模板

1
2
3
4
5
6
7
8
9
10
11
void dfs(vector<vector<char> >& grid, int i, int j) {
    if (!isInAread(grid, i, j)) { // 判断是否越界
        return;
    }
    // do something
    dfs(grid, i-1, j); // 上
    dfs(grid, i, j+1); // 右
    dfs(grid, i+1, j); // 下
    dfs(grid, i, j-1); // 左
    // do something
}

然后，考虑要对哪些位置 dfs 以及 dfs 过程中做什么操作、判断什么条件。

解法

方法一 边查边改

直接用模板，对所有的 O 进行 dfs，去判断每一个 O 四个方向上是否都可以通往 X，若是，则将 O 改为 X。

暂时没整出来优雅的代码

代码

1
2
// FBI WARNING
// TODO
  • 时间复杂度 O(m*n)
  • 空间复杂度 O(m*n)

方法二 先污染再治理

首先注意到，边界上的 O 是肯定不会改变的，只有内圈的才有可能改变。那么，换种思路

  • 先污染：把所有的内圈 O 变成中间状态 W；
  • 再治理：判断并修改中间状态 W 的最后状态。

如何判断？应该从恒定的初始位置状态出发，也就是边界上的 O。

  • 从每个边界上的 O出发执行 dfs，将dfs过程中遇到的中间状态 W 都给改成 O （说明这个原始 O 没有被封闭）；
  • 最后将剩下的中间状态 W 改成 最终状态 X。

代码

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
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>

using namespace std;

void dfs(vector<vector<char> >& board, int i, int j) {
    int m = board.size(), n = board[0].size();
    // cout << i << " " <<j << endl;
    if (i == m || j == n || i < 0 || j < 0 || board[i][j] != 'W') {
        return;
    }
    board[i][j] = 'O';
    dfs(board, i-1, j);
    dfs(board, i+1, j);
    dfs(board, i, j+1);
    dfs(board, i, j-1);
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<char> > board(m, vector<char>(n));
    for (int i=0; i<m; ++i) {
        for (int j=0; j<n; ++j) {
            cin >> board[i][j];
            if (board[i][j] == 'O') {
                board[i][j] = 'W';
            }
        }
    }
    cout << endl;
    for (int i=0; i<m; ++i) {
        dfs(board, i, 0);
        dfs(board, i, n-1);
    }
    for (int j=0; j<n; ++j) {
        dfs(board, 0, j);
        dfs(board, m-1, j);
    }
    for (int i=0; i<m; ++i) {
        for (int j=0; j<n; ++j) {
            if (board[i][j] == 'W') {
                board[i][j] = 'X';
            }
            cout << board[i][j];
        }
        cout << endl;
    }
    return 0;
}
  • 时间复杂度 O(m*n)
  • 空间复杂度 O(m*n)