当前位置： 面试刷题>> 炸弹袭击 (经典算法题500道)
### 题目描述补充
**题目：炸弹袭击（Grid Bombing）**
在一个N×M的网格中，每个格子可以放置一个炸弹或者为空。当炸弹爆炸时，它会以其所在位置为中心，向上、下、左、右四个方向扩散，直到遇到网格边界或另一个炸弹为止。现在，给定一个网格的初始状态（包含炸弹和空位置），计算所有炸弹爆炸后，网格中剩余多少空格位置。
**输入**：
- 一个二维数组`grid`，其中`grid[i][j]`为`'B'`表示该位置有炸弹，为`'.'`表示该位置为空。
- 网格的行数`N`和列数`M`。
**输出**：
- 爆炸后剩余的空格位置数量。
### 示例
**输入**：
```
grid = [
['B', '.', '.', 'B', '.'],
['.', '.', 'B', '.', '.'],
['.', '.', '.', '.', '.'],
['B', '.', '.', '.', 'B'],
['.', '.', 'B', '.', '.']
]
N = 5, M = 5
```
**输出**：
```
7
```
**解释**：
网格中有四个炸弹，爆炸后，只有7个空格位置未被破坏。
### PHP 示例代码
```php
function countRemainingSpaces($grid) {
$N = count($grid);
$M = count($grid[0]);
$visited = array_fill(0, $N, array_fill(0, $M, false));
$count = 0;
for ($i = 0; $i < $N; $i++) {
for ($j = 0; $j < $M; $j++) {
if ($grid[$i][$j] == 'B' && !$visited[$i][$j]) {
dfs($grid, $visited, $i, $j);
} elseif ($grid[$i][$j] == '.') {
$count++;
}
}
}
return $count;
}
function dfs(&$grid, &$visited, $i, $j) {
$N = count($grid);
$M = count($grid[0]);
$directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
$visited[$i][$j] = true;
foreach ($directions as $dir) {
$ni = $i + $dir[0];
$nj = $j + $dir[1];
if ($ni >= 0 && $ni < $N && $nj >= 0 && $nj < $M && !$visited[$ni][$nj] && $grid[$ni][$nj] == '.') {
$visited[$ni][$nj] = true;
dfs($grid, $visited, $ni, $nj);
}
}
}
// 示例用法
$grid = [
['B', '.', '.', 'B', '.'],
['.', '.', 'B', '.', '.'],
['.', '.', '.', '.', '.'],
['B', '.', '.', '.', 'B'],
['.', '.', 'B', '.', '.']
];
echo countRemainingSpaces($grid); // 输出 7
```
### Python 示例代码
```python
def count_remaining_spaces(grid):
N, M = len(grid), len(grid[0])
visited = [[False] * M for _ in range(N)]
count = 0
def dfs(i, j):
if i < 0 or i >= N or j < 0 or j >= M or visited[i][j] or grid[i][j] != '.':
return
visited[i][j] = True
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
dfs(i + dx, j + dy)
for i in range(N):
for j in range(M):
if grid[i][j] == 'B' and not visited[i][j]:
dfs(i, j)
elif grid[i][j] == '.':
count += 1
return count
# 示例用法
grid = [
['B', '.', '.', 'B', '.'],
['.', '.', 'B', '.', '.'],
['.', '.', '.', '.', '.'],
['B', '.', '.', '.', 'B'],
['.', '.', 'B', '.', '.']
]
print(count_remaining_spaces(grid)) # 输出 7
```
### JavaScript 示例代码
```javascript
function countRemainingSpaces(grid) {
const N = grid.length;
const M = grid[0].length;
const visited = Array.from({ length: N }, () => Array(M).fill(false));
let count = 0;
function dfs(i, j) {
if (i < 0 || i >= N || j < 0 || j >= M || visited[i][j] || grid[i][j] !== '.') {
return;
}
visited[i][j] = true;
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [dx, dy] of directions) {
dfs(i + dx, j + dy);
}
}
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (grid[i][j] === 'B' && !visited[i][j]) {
dfs(i, j);
} else if (grid[i][j] === '.') {
count++;
}
}
}
return count;
}
// 示例用法
const grid = [
['B', '.', '.', 'B', '.'],
['.', '.', 'B', '.', '.'],
['.', '.', '.', '.', '.'],
['B', '.', '.', '.', 'B'],
['.', '.', 'B', '.', '.']
];
console.log(countRemainingSpaces(grid)); // 输出 7
```
**码小课网站中有更多相关内容分享给大家学习**，包括但不限于算法题解、数据结构、编程技巧等，欢迎访问码小课网站深入学习。