题目描述补充

题目：炸弹袭击（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 示例代码

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 示例代码

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 示例代码

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

码小课网站中有更多相关内容分享给大家学习，包括但不限于算法题解、数据结构、编程技巧等，欢迎访问码小课网站深入学习。