130. 被围绕的区域【BFS】【DFS】

题目

题目

思路

1、边界处的O肯定没有被包围；
2、跟边界处的O连通的O也不能被包围；
3、所有不被包围的O，肯定跟某个边界处的O连通；
所以，问题转化为标记，哪些O是边界或与边界连通的，先暂时标记为A；

代码BFS

package main

func solve(board [][]byte) {
    bfs(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肯定没有被包围，跟边界处的O连通的O也不被包围；
所有不被包围的O，肯定跟某个边界处的O连通；
所以问题转化为标记，哪些O是边界或与边界连通的，先暂时标记为A；
*/
func bfs(board [][]byte) {
    // fmt.Printf("start is %v\n\n\n", board)

    if len(board) == 0 || len(board[0]) == 0 {
        return
    }

    // 现将边界处全部入队
    queue := make([][2]int, 0, 0) // 队列，所以slice；xy坐标所以[2]int

    m, n := len(board), len(board[0]) // m行n列
    for i := 0; i < m; i++ {
        if board[i][0] == 'O' {
            queue = append(queue, [2]int{i, 0})  // 第1列
        }
        if board[i][n-1] == 'O' {
            queue = append(queue, [2]int{i, n-1})  // 最后1列
        }
    }

    for j := 1; j<n-1; j++ {
        if board[0][j] == 'O' {
            queue = append(queue, [2]int{0, j})  // 第1行
        }
        if board[m-1][j] == 'O' {
            queue = append(queue, [2]int{m-1, j})  // 最后1行
        }
    }

    // 上下右左，偏移
    deltaX := [4]int{1,-1,0,0}
    delteY := [4]int{0,0,1,-1}

    for len(queue) > 0 {
        grid := queue[0]   // 取队列首个节点
        queue = queue[1:]  // 出队

        board[grid[0]][grid[1]] = 'A'   // 标记为访问
        // 将邻接的入队
        for i:=0; i<4; i++ {
            x := grid[0] + deltaX[i]  // 行
            y := grid[1] + delteY[i]  // 列

            if x<0 || x>m-1 || y<0 || y>n-1 || board[x][y] != 'O' {   // 越界的，或已访问过的，或不是'O'
                continue
            }

            queue = append(queue, [2]int{x, y})
        }
    }

    // fmt.Printf("end is %v\n\n\n", board)
    // 把'O'全换成'X', 把'A'全换成'O'
    for i := 0; i<m; i++ {
        for j := 0; j<n; j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X'
            }

            if board[i][j] == 'A' {
                board[i][j] = 'O'
            }
        }
    }
}

BFS结果

代码DFS

func solve(board [][]byte) {
    if len(board) == 0 || len(board[0]) == 0 {
        return
    }

    m, n := len(board), len(board[0]) // m行n列
    for i := 0; i < m; i++ {
        if board[i][0] == 'O' {
            dfs(board, i, 0)
        }
        if board[i][n-1] == 'O' {
            dfs(board, i, n-1)
        }
    }

    for j := 1; j<n-1; j++ {
        if board[0][j] == 'O' {
            dfs(board, 0, j)
        }
        if board[m-1][j] == 'O' {
            dfs(board, m-1, j)
        }
    }

    // 把'O'全换成'X', 把'A'全换成'O'
    for i := 0; i<m; i++ {
        for j := 0; j<n; j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X'
            }

            if board[i][j] == 'A' {
                board[i][j] = 'O'
            }
        }
    }
}

/*
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肯定没有被包围，跟边界处的O连通的O也不被包围；
所有不被包围的O，肯定跟某个边界处的O连通；
所以问题转化为标记，哪些O是边界或与边界连通的，先暂时标记为A；
*/
func dfs(board [][]byte, row, col int) {
    m, n := len(board), len(board[0]) // m行n列
    if row > m || col > n {
        return
    }

    if board[row][col] != 'O' {  // 'X' 或者 'A'
        return
    }

    board[row][col] = 'A'  // 标记为访问

    // 进行dfs
    // 1如果不是第1行
    if row > 0 && board[row-1][col] == 'O' {
        dfs(board, row-1, col)
    }
    // 2如果不是最后1行
    if row < m-1 && board[row+1][col] == 'O' {
        dfs(board, row+1, col)
    }
    // 3如果不是第1列
    if col > 0 && board[row][col-1] == 'O' {
        dfs(board, row, col-1)
    }
    // 4如果不是最后1列
    if col < n-1 && board[row][col+1] == 'O' {
        dfs(board, row, col + 1)
    }
}

结果