DFS&BFS - 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.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

思路：

题目要求把所有被X包围的O变成X，可以先从四周边界处理，如果边界是O就用dfs对区域做标记，然后在对中间区域做dfs，将所有连通分量O变成X。这里就需要一个visited二维数组来记录被访问过的点，开辟了额外的空间。另一种思路就是，在对四周边界做dfs的时候，就把原来的值给替换掉，然后遍历一遍二维数组，遇到O就换为X，遇到替换值就换为O。

代码：

go：

/*func solve(board [][]byte)  {

    if board == nil || len(board) == 0 || len(board[0]) == 0 {
        return 
    }
    
    row, col := len(board), len(board[0])
    var visited = make([][]bool, row)
    for i := range visited {
        visited[i] = make([]bool, col)
    }
    
    // 1.处理边界
    for j := 0; j < col; j++ {
        if board[0][j] == 'O' {
            dfs(&board, 0, j, row, col, &visited, false)
        }
        if board[row-1][j] == 'O' {
            dfs(&board, row -1, j, row, col, &visited, false)
        }
    }  
    for i := 0; i < row; i++ {
        if board[i][0] == 'O' {
            dfs(&board, i, 0, row, col, &visited, false)
        }
        
        if board[i][col-1] == 'O' {
            dfs(&board, i, col - 1, row, col, &visited, false)
        }
    }
    
    // 2. 常规dfs翻转剩下所有被包围的O
    
    for i := 1; i < row; i++ {
        for j := 1; j < col; j++ {
            if board[i][j] == 'O' {
                dfs(&board, i, j, row, col, &visited, true)
            }
        }
    } 
}

var dirs = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func dfs(board *[][]byte, i, j int, row, col int, visited *[][]bool, flip bool) {
    if i < 0 || i >= row || j < 0 || j >= col || (*visited)[i][j] || (*board)[i][j] == 'X'{
        return 
    }
    
    if flip {
        (*board)[i][j] = 'X'
    }
    (*visited)[i][j] = true
    
    for _, dir := range dirs {
        dfs(board, i + dir[0], j + dir[1], row, col, visited, flip)
    }
}*/

func solve(board [][]byte)  {
    if len(board) == 0 || len(board[0]) == 0 {
        return 
    }
    
    // 将与边界相邻的位置做标记
    for i := 0; i < len(board); i++ {
        if board[i][0] == 'O' {
            dfs(board, i, 0)
        }
        if board[i][len(board[0])-1] == 'O' {
            dfs(board, i, len(board[0])-1)
        }
    }
    
    for i := 0; i < len(board[0]); i++ {
        if board[0][i] == 'O' {
            dfs(board, 0, i)
        }
        if board[len(board)-1][i] == 'O' {
            dfs(board, len(board)-1, i)
        }
    }
    
    // 将所有标记的位置重置为 'O', 并将没有设置标记的位置设为 'X'
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            if board[i][j] == '*' {
                board[i][j] = 'O'
            } else if board[i][j] == 'O' {
                board[i][j] = 'X'
            }
        }
    }
}

func dfs(board [][]byte, i, j int) {
    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] != 'O' {
        return  
    }
    
    // 设置标记
    board[i][j] = '*'
    
    // 向四个方向移动
    dfs(board, i+1, j)
    dfs(board, i-1, j)
    dfs(board, i, j+1)
    dfs(board, i, j-1)
}