130.被围绕的区域

广度优先遍历

时间复杂度：O(n×m)
空间复杂度：O(n×m)

m,n为矩阵的行数和列数。

func solve(board [][]byte)  {
    rows := len(board)
    cols := len(board[0])

    dx := []int{-1, 0, 0, 1}
    dy := []int{0, -1, 1, 0}

    q := [][]int{}

    var bfs func(int, int)

    bfs = func(x int, y int) {
        q = q[1:]

        for i := 0; i < 4; i++ {
            nx := x + dx[i]
            ny := y + dy[i]

            if nx >= 0 && nx < rows && ny >= 0 && ny < cols && board[nx][ny] == 'O' {
                q = append(q, []int{nx, ny})
                board[nx][ny] = '#'
            }
        }
    }

	// 先处理四周的岛屿
    for i := 0; i < rows; i++ {
        if board[i][0] == 'O' {
            q = append(q, []int{i, 0})
            board[i][0] = '#'
        }
        if board[i][cols - 1] == 'O' {
            q = append(q, []int{i, cols - 1})
            board[i][cols-1] = '#'
        }
    }

    for i := 1; i < cols - 1; i++ {
        if board[0][i] == 'O' {
            q = append(q, []int{0, i})
            board[0][i] = '#'
        }
        if board[rows-1][i] == 'O' {
            q = append(q, []int{rows - 1, i})
            board[rows-1][i] = '#'
        }
    }

    // fmt.Printf("board: %v\n", board)

    for len(q) > 0 {
        bfs(q[0][0], q[0][1])
    }

	// 剩下的岛屿就是被围绕的岛屿，同时把四周的岛屿还原
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if board[i][j] == '#' {
                board[i][j] = 'O'
            } else if board[i][j] == 'O' {
                board[i][j] = 'X'
            }
        }
    }

}