题目

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

let board = [
    ["X", "X", "X", "X"],
    ["X", "O", "O", "X"],
    ["X", "X", "O", "X"],
    ["X", "O", "X", "X"]
]

运行你的函数后，矩阵变为：

board = [
    ["X", "X", "X", "X"],
    ["X", "X", "X", "X"],
    ["X", "X", "X", "X"],
    ["X", "O", "X", "X"]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/surrounded-regions

思路

找出所有边界上的’O’，并从边界上的’O’开始寻找相邻的’O’

• 对于每一个边界上的 O，以它为起点，标记所有与它直接或间接相连的字母 O；
• 最后遍历这个矩阵，对于每一个字母：
  • 如果该字母被标记过，则该字母为没有被字母 X 包围的字母 O，我们将其还原为字母 O；
  • 如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，我们将其修改为字母 X。

深度优先搜索

let row, col = 0;
function solve(board) {
    if (board == null || board.length == 0) {
        return;
    }
    row = board.length;
    col = board[0].length;
    for (let c = 0; c < col; c++) {	// 对矩阵的第一行与最后一行进行遍历
        dfs(board, 0, c);
        dfs(board, row - 1, c);
    }
    for (let r = 1; r < row - 1; r++) {	// 对矩阵的第一列与最后一列进行遍历（排除前一个for循环中包含的端点）
        dfs(board, r, 0);
        dfs(board, r, col - 1);
    }
    for (let i = 0; i < row; i++) {	// 深度优先搜索结束后，遍历矩阵，将为'O'的置为'X',将标记过的值还原为'O'
        for (let j = 0; j < col; j++) {
            board[i][j] === "O" && (board[i][j] = "X");
            board[i][j] === "Y" && (board[i][j] = "O");
        }
    }
};

// 深度优先搜索
function dfs(board, x, y) {
	// 判断是否越界，矩阵值是否为'O'
    if (x < 0 || y < 0 || x >= row || y >= col || board[x][y] != "O") {
        return;
    }
    // 满足条件，进行标记
    board[x][y] = "Y";
    // 对其四周的值进行深度优先搜索
    dfs(board, x + 1, y);
    dfs(board, x, y + 1);
    dfs(board, x, y - 1);
    dfs(board, x - 1, y);
}

广度优先搜索

let row, col = 0;
function solve(board) {
    const dx = [1, -1, 0, 0];
    const dy = [0, 0, 1, -1];
    if (board == null || board.length == 0) {
        return;
    }
    row = board.length;
    col = board[0].length;
    let quene = [];	// 初始化队列
    for (let c = 0; c < col; c++) {		// 首行与末行
        if (board[0][c] === "O") {
            quene.push([0, c])	// 放入队列
        }
        if (board[row - 1][c] === "O") {
            quene.push([row - 1, c])
        }
    }
    for (let r = 1; r < row - 1; r++) {	// 首列与末列
        if (board[r][0] === "O") {
            quene.push([r, 0])
        }
        if (board[r][col - 1] === "O") {
            quene.push([r, col - 1])
        }
    }
    while (quene.length > 0) {	// 循环直至队列为空
        let x = quene[0][0];
        let y = quene[0][1];
        quene.shift();	// 移出队列
        board[x][y] = "Y";	
        for (let i = 0; i < 4; i++) {	// 将当前位置四周为'O'的坐标放入队列中
            let mx = x + dx[i];
            let my = y + dy[i];
            if (mx < 0 || my < 0 || mx >= row || my >= col || board[mx][my] != "O") {
                continue;
            }
            quene.push([mx, my])
        }
    }
	// 广度优先搜索结束后，遍历矩阵，将为'O'的置为'X',将标记过的值还原为'O'
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            board[i][j] === "O" && (board[i][j] = "X");
            board[i][j] === "Y" && (board[i][j] = "O");
        }
    }
};