当前位置： 面试刷题>> 被围绕的区域(经典算法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 示例代码
```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 示例代码
```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 示例代码
```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。