130 Surrounded Regions

发表于 | 分类于 | |

130. Surrounded Regions

题目描述

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example,

1
2
3
4
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

1
2
3
4
X X X X
X X X X
X X X X
X O X X

题目大意

将矩阵中，被X包围的所有O都变为X。

解题思路

从四边开始遍历，如果边缘有O,则继续进行广度遍历，将相连的O标记为#。
遍历矩阵，则剩下的O便为被X包围的，即修改为X；将标记为#的修改为O。

代码

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
func solve(_ board: inout [[Character]]) {
        func bfs(x: Int, y: Int) {
            guard board[x][y] == "O" else { return }
            board[x][y] = "#"
            var queue = [(x, y)]
            while !queue.isEmpty {
                let top = queue.removeLast()
                if top.0 > 0 && board[top.0 - 1][top.1] == "O" {
                    board[top.0 - 1][top.1] = "#"
                    queue.append((top.0 - 1, top.1))
                }
                if top.0 < board.count - 1 && board[top.0 + 1][top.1] == "O" {
                    board[top.0 + 1][top.1] = "#"
                    queue.append((top.0 + 1, top.1))
                }
                if top.1 > 0 && board[top.0][top.1 - 1] == "O" {
                    board[top.0][top.1 - 1] = "#"
                    queue.append((top.0, top.1 - 1))
                }
                if top.1 < board[0].count - 1 && board[top.0][top.1 + 1] == "O" {
                    board[top.0][top.1 + 1] = "#"
                    queue.append((top.0, top.1 + 1))
                }
            }
        }
        guard board.count > 2 && board[0].count > 2 else { return }
        for j in 0..<board[0].count {
            bfs(x: 0, y: j)
            bfs(x: board.count - 1, y: j)
        }
        for i in 1..<board.count - 1 {
            bfs(x: i, y: 0)
            bfs(x: i, y: board[0].count - 1)
        }
        for i in 0..<board.count {
            for j in 0..<board[i].count {
                if board[i][j] == "O" {
                    board[i][j] = "X"
                }else if board[i][j] == "#" {
                    board[i][j] = "O"
                }
            }
        }
    }
0%