这道题本质上是图的连通性问题。通过行列坐标可以构造出无向图。然后DFS遍历每一个节点,数算出图中所有连通的节点数。需要注意的是每次出发的起点不要计算,因为删除到最后每个连通子图需要留下至少一个点。这个方法是通用的,不论在什么规则下导致两点连通,我们都可以用这种方法先构造出adjacent map。下次即使对角线上的点也连通,也可以用这种方法。

var removeStones = function(stones) {
    const len = stones.length;
    if (len <= 1) {
        return 0;
    }
    const map = {};
    for (let i = 0; i< len; i++) {
        for (let j = i+1; j < len; j++) {
            if (stones[i][0] === stones[j][0] || stones[i][1] === stones[j][1]) {
                if (i in map) {
                    map[i].push(j);
                } else {
                    map[i] = [j];
                }
                if (j in map) {
                    map[j].push(i);
                } else {
                    map[j] = [i];
                }
            }
        }
    }

    const visited = new Array(len);
    for (let i = 0; i < len; i++) {
        visited[i] = false;
    }

    let res = 0;
    for (let i = 0; i < len; i++) {
        res += dfs(i, visited, map, true);
    }
    return res;
};

function dfs(curr, visited, map, isStart) {
    if (visited[curr]) {
        return 0;
    }
    if (!(curr in map)) {
        return 0;
    }
    visited[curr] = true;
    const neighbors = map[curr];
    let res = isStart ? 0 : 1;
    for (let i = 0; i < neighbors.length; i++) {
        res += dfs(neighbors[i], visited, map, false);
    }
    return res;
}

results matching ""

    No results matching ""