LeetCode 130. Surrounded Regions

Problem

LeetCode 130. Surrounded Regions

1. 题目简述

给出一个由’O’和’X’组成的二维数组，将所有由‘X’包围的‘O’替换成‘X’。例如：

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

2. 算法思路

相关问题：

1. LeetCode 200. Number of Islands(无解析)

DFS || BFS

1. 先将和边界相连的所有‘O’都替换成另一个字母‘W’，这里DFS或者BFS都可以（这里以DFS为例）；
2. 然后将board中剩余的‘O’都替换成’X‘；
3. 将替换后的board中的’W‘再替换回去。

这里需要注意的只有我们用了一个Pair的List来记录了初始和边界相连的’O‘的位置，第三部只需要一个个遍历换回去即可。

class Solution {
    int[][] directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    public void solve(char[][] board) {
        // DFS，先将所有从边界出发的“O”替换为“W”，然后将board中所有的“O”替换成“X”，然后再替换回来

        // 判断输入为空的情况
        if (board == null || board.length == 0) {
            return;
        }

        // 遍历四周，将与边相连的“O”变为“W”
        int m = board.length, n = board[0].length;
        List<Pair<Integer, Integer>> list = new ArrayList();
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                replace(board, i, 0, 'O', 'W', list);
            }
            if (board[i][n - 1] == 'O') {
                replace(board, i, n - 1, 'O', 'W', list);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                replace(board, 0, j, 'O', 'W', list);
            }
            if (board[m - 1][j] == 'O') {
                replace(board, m - 1, j, 'O', 'W', list);
            }
        }

        // 遍历全局，找出所有的剩余的‘O’替换为‘X’
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }

        // 恢复‘W’为‘O’
        for (Pair<Integer, Integer> pair : list) {
            board[pair.getKey()][pair.getValue()] = 'O';
        }

    }

    // 替换与边界相连的O为W
    private void replace(char[][] board, int row, int col, char replace, char target, List<Pair<Integer, Integer>> list) {
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
            return;
        }

        if (board[row][col] == replace) {
            list.add(new Pair<Integer, Integer>(row, col));
            board[row][col] = target;
            for (int[] direction : directions) {
                replace(board, row + direction[0], col + direction[1], replace, target, list);
            }
        }
    }
}