当前位置: 面试刷题>> 被围绕的区域(经典算法150题)


题目描述

给定一个二维的0和1的矩阵(grid),其中0表示空地,1表示建筑物。一个建筑物如果所有四个方向(上、下、左、右)的相邻格子都是空地(0)或超出了矩阵的边界,那么这个建筑物就是“被围绕的”。请编写一个算法,输出一个与原始矩阵相同大小的矩阵,但是其中所有被围绕的建筑物(即值为1的格子)被翻转为0,而所有其他格子保持不变。

示例

输入:

grid = [
  [1,1,1],[
  [1,0,1],
  [1,1,1]
]

输出:

[
  [1,0,1],
  [1,0,1],
  [1,0,1]
]

解释:所有的建筑物都被围绕了,因此它们都被翻转成了0。

PHP 示例代码

function solve($grid) {
    if (empty($grid) || empty($grid[0])) return $grid;

    $rows = count($grid);
    $cols = count($grid[0]);

    // 从边界开始,将所有与边界相连的1标记为2(视为非被围绕)
    for ($i = 0; $i < $rows; $i++) {
        if ($grid[$i][0] == 1) dfs($grid, $i, 0);
        if ($grid[$i][$cols - 1] == 1) dfs($grid, $i, $cols - 1);
    }

    for ($j = 0; $j < $cols; $j++) {
        if ($grid[0][$j] == 1) dfs($grid, 0, $j);
        if ($grid[$rows - 1][$j] == 1) dfs($grid, $rows - 1, $j);
    }

    // 将剩余的1(即被围绕的)翻转为0,将2(非被围绕的)翻转回1
    for ($i = 0; $i < $rows; $i++) {
        for ($j = 0; $j < $cols; $j++) {
            if ($grid[$i][$j] == 2) {
                $grid[$i][$j] = 1;
            } elseif ($grid[$i][$j] == 1) {
                $grid[$i][$j] = 0;
            }
        }
    }

    return $grid;
}

function dfs(&$grid, $row, $col) {
    $rows = count($grid);
    $cols = count($grid[0]);
    if ($row < 0 || $row >= $rows || $col < 0 || $col >= $cols || $grid[$row][$col] != 1) {
        return;
    }
    $grid[$row][$col] = 2;
    dfs($grid, $row - 1, $col);
    dfs($grid, $row + 1, $col);
    dfs($grid, $row, $col - 1);
    dfs($grid, $row, $col + 1);
}

// 示例用法
$grid = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
];
$result = solve($grid);
print_r($result);

Python 示例代码

def solve(grid):
    if not grid or not grid[0]:
        return grid

    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return
        grid[r][c] = 2
        dfs(r - 1, c)
        dfs(r + 1, c)
        dfs(r, c - 1)
        dfs(r, c + 1)

    # 标记与边界相连的1为2
    for i in range(rows):
        if grid[i][0] == 1: dfs(i, 0)
        if grid[i][cols - 1] == 1: dfs(i, cols - 1)
    for j in range(cols):
        if grid[0][j] == 1: dfs(0, j)
        if grid[rows - 1][j] == 1: dfs(rows - 1, j)

    # 将剩余的1翻转为0,2翻转回1
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 2:
                grid[i][j] = 1
            elif grid[i][j] == 1:
                grid[i][j] = 0

    return grid

# 示例用法
grid = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]
result = solve(grid)
print(result)

JavaScript 示例代码

function solve(grid) {
    if (!grid.length || !grid[0].length) return grid;

    const rows = grid.length;
    const cols = grid[0].length;

    function dfs(r, c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== 1) return;
        grid[r][c] = 2;
        dfs(r - 1, c);
        dfs(r + 1, c);
        dfs(r, c - 1);
        dfs(r, c + 1);
    }

    // 标记与边界相连的1为2
    for (let i = 0; i < rows; i++) {
        if (grid[i][0] === 1) dfs(i, 0);
        if (grid[i][cols - 1] === 1) dfs(i, cols - 1);
    }
    for (let j = 0; j < cols; j++) {
        if (grid[0][j] === 1) dfs(0, j);
        if (grid[rows - 1][j] === 1) dfs(rows - 1, j);
    }

    // 将剩余的1翻转为0,2翻转回1
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === 2) grid[i][j] = 1;
            else if (grid[i][j] === 1) grid[i][j] = 0;
        }
    }

    return grid;
}

// 示例用法
const grid = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
];
const result = solve(grid);
console.log(result);

这些示例代码均展示了如何使用深度优先搜索(DFS)来找到并标记与边界相连的建筑物,然后将剩余的建筑物(即被围绕的)翻转为0。

推荐面试题