[LeetCode] 130. Surrounded Regions

You are given an m x n matrix board containing letters ‘X’ and ‘O’, capture regions that are surrounded:

Connect: A cell is connected to adjacent cells horizontally or vertically.
Region: To form a region connect every ‘O’ cell.
Surround: The region is surrounded with ‘X’ cells if you can connect the region with ‘X’ cells and none of the region cells are on the edge of the board.
A surrounded region is captured by replacing all ‘O’s with ‘X’s in the input matrix board.

Example 1:

Input: board = [[“X”,”X”,”X”,”X”],[“X”,”O”,”O”,”X”],[“X”,”X”,”O”,”X”],[“X”,”O”,”X”,”X”]]
Output: [[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”O”,”X”,”X”]]

Explanation:
In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2:
Input: board = [[“X”]]
Output: [[“X”]]

Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is ‘X’ or ‘O’.

被围绕的区域。

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：

连接：一个单元格与水平或垂直方向上相邻的单元格连接。
区域：连接所有 ‘O’ 的单元格来形成一个区域。
围绕：如果您可以用 ‘X’ 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 ‘X’ 单元格围绕。

通过将输入矩阵 board 中的所有 ‘O’ 替换为 ‘X’ 来 捕获被围绕的区域。

思路

这道题就是一般的 BFS/DFS 题目，这里我给出两种做法。其中我觉得DFS比较简单，实现起来不容易错。题意很简单但是注意一个边界条件。题目要你将所有被包围的 O 用 X 填充，但是不包括矩阵边界的 O。

具体地，我们需要对矩阵扫描三遍
第一次遍历首先要扫描矩阵的四条边，看看四个 border 上是否有 O，如果有，则需要 DFS 遍历，找出所有跟这个边界上的 O 联通的 O 并且把他们标记成一个别的东西。我这里是标记成 N。标记说明这些坐标是不能被改成 X 的。

第二次遍历，如果当前坐标上是 O, 则说明这个 O 不在边界上，则可以将这个坐标变成 X。

第三次遍历，将矩阵内的 N 再变回 O。这些坐标是不能被改成 X 的。

复杂度

时间O(mn)
空间O(mn)

DFS代码

Java实现

class Solution {
    int m;
    int n;
    
    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        // 找到边缘上的O，改成N
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
                    if (board[i][j] == 'O') {
                        dfs(board, i, j);
                    }
                }
            }
        }
        
        // 找到内圈的O，改成X
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
        
        // 把N再改回成O
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'N') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] != 'O') {
            return;
        }
        board[i][j] = 'N';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
}

BFS代码

Java实现

class Solution {
	public void solve(char[][] board) {
		int m = board.length;
		int n = board[0].length;
		Queue<int[]> queue = new LinkedList<>();
		// 找到边缘上的O，改成N
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
					if (board[i][j] == 'O') {
						board[i][j] = 'N';
						queue.offer(new int[] { i, j });
					}
				}
			}
		}

		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int x = cur[0];
			int y = cur[1];
			for (int k = 0; k < 4; k++) {
				int newX = x + dx[k];
				int newY = y + dy[k];
				if (newX >= 0 && newX < m && newY >= 0 && newY < n && board[newX][newY] == 'O') {
					board[newX][newY] = 'N';
					queue.offer(new int[] { newX, newY });
				}
			}
		}

		// 找到内圈的O，改成X
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
        
        // 把N再改回成O
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'N') {
                    board[i][j] = 'O';
                }
            }
        }
	}
}