130. 被围绕的区域

题目描述

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例 1：

输入：board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]]
输出：[[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [[“X”]]
输出：[[“X”]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'

解法一：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
41


func solve(board [][]byte) {
    h, w := len(board), len(board[0])
    visited := make([][]bool, h)
    for i := 0; i < h; i++ {
        visited[i] = make([]bool, w)
    }
    dirs := [][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
    var dfs func(i, j int)
    dfs = func(i, j int) {
        visited[i][j] = true
        for _, dir := range dirs {
            ni, nj := i + dir[0], j + dir[1]
            if 0 <= ni && ni < h && 0 <= nj && nj < w && board[ni][nj] == 'O' && !visited[ni][nj] {
                dfs(ni, nj)
            }
        }
    }
    for j := 0; j < w; j++ {
        if board[0][j] == 'O' && !visited[0][j] {
            dfs(0, j)
        }
        if board[h-1][j] == 'O' && !visited[h-1][j] {
            dfs(h-1, j)
        }
    }
    for i := 1; i < h -1; i++ {
        if board[i][0] == 'O' && !visited[i][0] {
            dfs(i, 0)
        }
        if board[i][w-1] == 'O' && !visited[i][w-1] {
            dfs(i, w-1)
        }
    }
    for i := 0; i < h; i++ {
        for j := 0; j < w; j++ {
            if board[i][j] == 'O' && !visited[i][j] {
                board[i][j] = '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


var n, m int

func solve(board [][]byte)  {
    if len(board) == 0 || len(board[0]) == 0 {
        return
    }
    n, m = len(board), len(board[0])
    for i := 0; i < n; i++ {
        dfs(board, i, 0)
        dfs(board, i, m - 1)
    }
    for i := 1; i < m - 1; i++ {
        dfs(board, 0, i)
        dfs(board, n - 1, i)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if board[i][j] == 'A' {
                board[i][j] = 'O'
            } else if board[i][j] == 'O' {
                board[i][j] = 'X'
            }
        }
    }
}

func dfs(board [][]byte, x, y int) {
    if x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O' {
        return
    }
    board[x][y] = 'A'
    dfs(board, x + 1, y)
    dfs(board, x - 1, y)
    dfs(board, x, y + 1)
    dfs(board, x, y - 1)
}

解法二：BFS

 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 [][]byte) {
    h, w := len(board), len(board[0])
    visited := make([][]bool, h)
    for i := 0; i < h; i++ {
        visited[i] = make([]bool, w)
    }
    dirs := [][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
    var bfs func(i, j int)
    bfs = func(i, j int) {
        visited[i][j] = true
        var queue [][2]int
        queue = append(queue, [2]int{i, j})
        for len(queue) > 0 {
            coordinate := queue[0]
            x, y := coordinate[0], coordinate[1]
            queue = queue[1:]
            for _, dir := range dirs {
                nx, ny := x+dir[0], y+dir[1]
                if 0 <= nx && nx < h && 0 <= ny && ny < w && board[nx][ny] == 'O' && !visited[nx][ny] {
                    visited[nx][ny] = true
                    queue = append(queue, [2]int{nx, ny})
                }
            }
        }
    }
    for j := 0; j < w; j++ {
        if board[0][j] == 'O' && !visited[0][j] {
            bfs(0, j)
        }
        if board[h-1][j] == 'O' && !visited[h-1][j] {
            bfs(h-1, j)
        }
    }
    for i := 1; i < h-1; i++ {
        if board[i][0] == 'O' && !visited[i][0] {
            bfs(i, 0)
        }
        if board[i][w-1] == 'O' && !visited[i][w-1] {
            bfs(i, w-1)
        }
    }
    for i := 0; i < h; i++ {
        for j := 0; j < w; j++ {
            if board[i][j] == 'O' && !visited[i][j] {
                board[i][j] = 'X'
            }
        }
    }
}