20. 炸弹人的雷区数量[200分]

题目内容

在一款游戏中设计炸弹人技能效果是预埋地雷，当敌人从地雷上走过时会触发地雷爆炸造成伤害。当一个地雷被引爆时，在一定距离内的相邻的地雷也会引爆，这些能够同时引爆的地雷形成一个雷区。一个雷区可以由一枚孤立的地雷组成，也可以由一片有连锁爆炸反应的多枚地雷组成。现给出一组炸弹人地雷连锁爆炸关联数据，请计算有效雷区数量。

输入描述

地雷连锁爆炸信息记录在一个 n × n 的二维数组 isChainExplosion 中：

• isChainExplosion[i][j] = 1：第 i 枚地雷和第 j 枚地雷有互相引爆关系
• isChainExplosion[i][j] = 0：第 i 枚地雷和第 j 枚地雷不会被彼此引爆

输入用例保证：

• isChainExplosion[i][i] 和 isChainExplosion[j][j] 的值同时为 0 或者同时为 1
• 地雷数量 n：1 ≤ n ≤ 20

输出描述

输出有效雷区数量。

样例

样例 1

输入

1,0
0,1

输出

2

说明： 两枚地雷互相独立，其中一枚被引爆时不会触发另一枚地雷，所以雷区数量是 2。

样例 2

输入

1,0,0
0,1,1
0,1,1

输出

2

说明： 三枚地雷中，第一枚和第二、第三枚互相独立，第二枚和第三枚临近且引爆，因此雷区数量是 2。

样例 3

输入

1,1,1
1,1,1
1,1,1

输出

1

说明： 全连通场景，三枚地雷两两直接互相引爆，形成一个雷区。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let lines = [];
rl.on('line', (input) => {
    lines.push(input.split(',').map(Number));
});

rl.on('close', () => {
    const n = lines.length;          // 地雷数量
    const visited = new Array(n).fill(false);
    let ans = 0;

    // 从节点 u 出发，DFS 遍历它所在的连通分量
    const dfs = (u) => {
        for (let v = 0; v < n; v++) {
            // u 和 v 之间有引爆关系，且 v 还没访问过
            if (lines[u][v] === 1 && !visited[v]) {
                visited[v] = true;
                dfs(v);
            }
        }
    };

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            ans++;
            visited[i] = true;
            dfs(i);
        }
    }

    console.log(ans);
});