图论 岛屿问题 ACM 模式 JS

kama是卡码网 https://kamacoder.com/
没标记kama的是力扣

kama 98 所有可达路径

（1）从节点 0 出发，定义一个路径 path；
（2）每次走到一个节点 node，递归访问它的邻居节点；
（3）如果走到终点 n-1，就把当前 path 加入结果集；
（4）每次访问完一个邻居后，path.pop() 回溯，恢复现场。

与LCR 110相同

• 邻接矩阵版本

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

let inputLines = []
rl.on('line', (line) => {
    if (line.trim() !== '') {
        inputLines.push(line.trim());
    }
})

rl.on('close', () => {
    const [N, M] = inputLines[0].split(' ').map(Number);
    const graph = Array.from({ length: N+1 }, () => []);
    for (let i = 1; i <= M; i++) {
        const [a, b] = inputLines[i].split(' ').map(Number);
        graph[a].push(b);
    }

    const result = [];
    const path = [1];
    const dfs = (index) => {
        if (index === N) {
            result.push([...path]);
            // console.log(path.join(' '));
            return;
        }

        for (const next of graph[index]) {
            path.push(next);
            dfs(next);
            path.pop();
        }
    }

    dfs(1);
    if (result.length > 0) {
        result.forEach(p => console.log(p.join(' ')));
    } else {
        console.log(-1);
    }

})

kama 99

https://kamacoder.com/problempage.php?pid=1171

const readline = require('readline')

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

let inputLines = []
rl.on('line', (line) => {
    if (line.trim() !== '') {
        inputLines.push(line);
    }
})

rl.on('close', () => {
    const [N, M] = inputLines[0].split(' ').map(Number);
    const grid = Array.from({ length: N }, () => []);
    for (let i = 1; i <= N; i++) {
        grid[i - 1] = inputLines[i].split(' ');
    }

    console.log(numIslands(grid));
})

// 直接调用了在力扣核心模式里面写的函数
const numIslands = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
     const dfs = (grid, x, y) => {
        if(x < 0 || y < 0 || x >= m || y >= n || grid[x][y] !== '1') {
            return;
        }

        grid[x][y] = '2';
        dfs(grid, x-1, y);
        dfs(grid, x+1, y);
        dfs(grid, x, y-1);
        dfs(grid, x, y+1);
    }  
    let cnt = 0;
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(grid[i][j] === '1') {
                cnt++;
                dfs(grid, i, j);
            }
        }
    }
    return cnt;
   
};

200 岛屿数量（深搜）

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
     const dfs = (grid, x, y) => {
        if(x < 0 || y < 0 || x >= m || y >= n || grid[x][y] !== '1') {
            return;
        }

        grid[x][y] = '2';
        dfs(grid, x-1, y);
        dfs(grid, x+1, y);
        dfs(grid, x, y-1);
        dfs(grid, x, y+1);
    }  
    let cnt = 0;
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(grid[i][j] === '1') {
                cnt++;
                dfs(grid, i, j);
            }
        }
    }
    return cnt;
   
};

695 岛屿最大面积

和上一题很像，关键点用变量存储面积

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    const m = grid.length;
    const n = grid[0].length;

    const dfs = (grid, x, y) => {
        if(x < 0 || x >= m || y < 0 || y >= n || grid[x][y] !== 1) {
            return 0;
        }

        grid[x][y] = 2;
        let res = 1;
    // 每次递归返回的是该方向上的陆地面积，res += 将这些面积累加到当前单元格的面积中。
        res += dfs(grid, x+1, y);
        res += dfs(grid, x-1, y);
        res += dfs(grid, x, y+1);
        res += dfs(grid, x, y-1);
        return res;
    }

    let maxArea = 0;
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(grid[i][j] === 1) {
                maxArea = Math.max(dfs(grid, i, j),maxArea);
            }
        }
    }
    return maxArea;
};

kama 102 沉没孤岛

原先的思路是四周都是水打标记，然后把他淹没，其实不是，因为孤岛并不总是很小，且如果他弯弯曲曲，怎么判断的。所以思路是相反的，从陆地边缘出发“污染”掉所有不是孤岛的岛，污染之后复原。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

const readline = require('readline');

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

let M, N;
let lineCount = 0;
let grid = [];
rl.on('line', (line) => {
    if (line.trim() !== '') {
        if (lineCount === 0) {
            [M, N] = line.trim().split(' ').map(Number);
        } else {
            grid.push(line.trim().split(' ').map(Number));
        }
        lineCount++;
    }
})

rl.on('close', () => {

    const dfs = (grid, x, y) => {
        if (x < 0 || x >= M || y < 0 || y >= N || grid[x][y] !== 1) {
            return;
        }
        grid[x][y] = 2;
        // 四个方向递归
        dfs(grid, x - 1, y);
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
        dfs(grid, x, y + 1);
    }

    // 非孤岛
    for (let i = 0; i < M; i++) {
        for (let j = 0; j < N; j++) {
            if ((i === 0 || i === M - 1 || j === 0 || j === N - 1) && grid[i][j] === 1) {
                dfs(grid, i, j);
            }
        }
    }

    // 沉没孤岛
    for (let i = 0; i < M; i++) {
        for (let j = 0; j < N; j++) { 
            if (grid[i][j] === 1) {
                grid[i][j] = 0;
            } else if (grid[i][j] === 2) {
                grid[i][j] = 1;
            }
        }
    }

    // 打印
    // 输出结果（每个数字后带空格）
    for (let i = 0; i < M; i++) {
        let row = '';
        for (let j = 0; j < N; j++) {
            row += grid[i][j] + ' ';
        }
        console.log(row.trim());
    }
})

463 岛屿的周长

周长的记录：从岛屿跨越到水，也就是到边界的时候，周长+1。边界条件，从陆地->海，边长+1。从陆地->访问过的陆地，边长+0

/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function(grid) {
    const m = grid.length;
    const n = grid[0].length;

    const dfs = (x, y) => {
        if(x < 0 || x >= m || y < 0 || y >= n || grid[x][y] === 0) {
            return 1;
        }
        if (grid[x][y] === 2) {
            return 0;
        }

        grid[x][y] = 2;
        let res = 0;
        res += dfs(x+1, y);
        res += dfs(x-1, y);
        res += dfs(x, y+1);
        res += dfs(x, y-1);
        return res;
    }

    let c = 0;
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(grid[i][j] === 1) {
                c += dfs(i, j);
            }
        }
    }
    return c;
};

417 太平洋大西洋

https://leetcode.cn/problems/pacific-atlantic-water-flow/description/

每一个单元格都要dfs一遍，雨水降落到达边界。时间复杂度太高。返回来思考，从两个边界出发，递增。有两个岛，需要从指定的边界向内污染，可以提取一个公共的函数dfs(row,col,ocean)。这个dfs的作用是“污染”指定边界的区域，如果已经污染过，返回。这里也需要提前判断 newrow,newcol，但它在边界内且heights[newrow][newcol] >= heights[row][col]再dfs

/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function(heights) {
    const m = heights.length;
    const n = heights[0].length;

    const pacific = Array.from({length:m},()=>new Array(n).fill(false));
    const atlantic = Array.from({length:m},()=>new Array(n).fill(false));

    const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
    // 从上边界、左边界出发，值增长->true
    const dfsocean = (row, col, ocean) =>{
        if(ocean[row][col]) return;
        ocean[row][col] = true;

        for(const [dx,dy] of dirs) {
            let newrow = row + dx;
            let newcol = col + dy;
            if(newrow >= 0 && newrow < m && newcol >= 0 && newcol < n && heights[newrow][newcol] >= heights[row][col]) {
                dfsocean(newrow, newcol, ocean);
            }
        }
    }
    
    for(let i = 0; i < m; i++) {
        dfsocean(i, 0, pacific);
    }
    for(let i = 0; i < n; i++) {
        dfsocean(0, i, pacific);
    }

    for(let i = 0; i < m; i++) {
        dfsocean(i, n-1, atlantic);
    }
    for(let i = 0; i < n; i++) {
        dfsocean(m-1, i, atlantic);
    }
    let res = [];
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(pacific[i][j] && atlantic[i][j]) {
                let cell = [];
                cell.push(i);
                cell.push(j);
                res.push(cell);
            }
        }
    }
    return res;
};

827 最大人工岛

最多可以将一个水域变为陆地。（1）计算原始矩阵中所有岛屿的面积，并记录每个岛屿的大小（2）通过将一个水域变为陆地，可能会连接多个岛屿，从而形成更大的岛屿。（3）在所有可能的水域变陆地的操作中，找到能够形成最大岛屿的那个操作

var largestIsland = function(grid) {
    const area = [];
    const m = grid.length;
    const n = grid[0].length;

    const dfs = (x,y) => {
        if(x < 0 || x >= m || y < 0 || y >= n || grid[x][y] !== 1) {
            return 0;
        }
        grid[x][y] = area.length + 2;
        let a = 1;
        a += dfs(x+1, y);
        a += dfs(x-1, y);
        a += dfs(x, y+1);
        a += dfs(x, y-1);
        return a;
    }

    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(grid[i][j] === 1) {
                area.push(dfs(i,j));
            }
        }
    }

    if(area.length === 0) return 1;

    let ans = 0;
    const set = new Set();
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(grid[i][j] === 0){
                set.clear();
                let newArea = 1;
                for(const [dx, dy] of dirs) {
                    let x = i + dx;
                    let y = j + dy;
                    if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] !== 0 && !set.has(grid[x][y])) {
                        set.add(grid[x][y]);
                        newArea += area[grid[x][y] - 2]; // 累加面积
                    }
                }
                ans = Math.max(ans, newArea);
            }
        }
    }
    return ans || n * n;
};