200.岛屿数量

image.png
DFS：

  1. let direction = [
  2.     [1, 0], [0, 1], [-1, 0], [0, -1]
  3. ]
  4. /**
  5.  * @param {character[][]} grid
  6.  * @return {number}
  7.  */
  8. var numIslands = function (grid) {
  9.     let count = 0;
  10.     let row = grid.length;
  11.     let col = grid[0].length;
  12.     for (let i = 0; i < row; i++) {
  13.         for (let j = 0; j < col; j++) {
  14.             if (grid[i][j] === '1') {
  15.                 dfs(i, j);
  16.                 count++;
  17.             }
  18.         }
  19.     }
  20.     return count;
  22.     function dfs(x, y) {
  23.         if (x < 0 || y < 0 || x >= row || y >= col || grid[x][y] === '0') {
  24.             return;
  25.         }
  26.         grid[x][y] = '0';
  27.         for (let i = 0; i < 4; i++) {
  28.             let nextX = x + direction[i][0];
  29.             let nextY = y + direction[i][1];
  30.             dfs(nextX, nextY);
  31.         }
  32.     }
  33. };

BFS：

let direction = [
    [1, 0], [0, 1], [-1, 0], [0, -1]
]
Array.prototype.isEmpty = function () {
    return this.length === 0 ? true : false;
}
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    let count = 0;
    let row = grid.length;
    let col = grid[0].length;
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (grid[i][j] === '1') {
                bfs(i, j);
                count++;
            }
        }
    }
    return count;

    function bfs(x, y) {
        let queue = [];
        queue.push([x, y]);
        while (!queue.isEmpty()) {
            let cur = queue.shift();
            x = cur[0];
            y = cur[1];
            if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] === '1') {
                grid[x][y] = '0';
                for (let i = 0; i < 4; i++) {
                    let nextX = x + direction[i][0];
                    let nextY = y + direction[i][1];
                    queue.push([nextX, nextY]);
                }
            }
        }
    }
};

463.岛屿的周长

https://leetcode-cn.com/problems/island-perimeter/
QQ截图20210620165818.png

/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function (grid) {
    // 记录多少次到达边界，即周长
    let count = 0;
    let row = grid.length;
    let col = grid[0].length;
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (grid[i][j] === 1) {
                dfs(i, j);
            }
        }
    }
    return count;

    function dfs(x, y) {
          // 达到边界处就count+1
        if (x < 0 || y < 0 || x >= row || y >= col || grid[x][y] === 0) {
            count++;
            return;
        }
          // 到达走过的点就直接返回
        if (grid[x][y] === -1) {
            return;
        }
          // 走过的点标记为-1
        grid[x][y] = -1;
        dfs(x - 1, y);
        dfs(x, y - 1);
        dfs(x + 1, y);
        dfs(x, y + 1);
    }
};

5791.统计子岛屿

QQ截图20210620170550.png

/**
 * @param {number[][]} grid1
 * @param {number[][]} grid2
 * @return {number}
 */
var countSubIslands = function (grid1, grid2) {
    let count = 0;
    let row = grid1.length;
    let col = grid1[0].length;
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (grid2[i][j] === 1) {
                let res = dfs(i, j);
                // true表示符合
                if (res === true) {
                    count++;
                }
            }
        }
    }
    return count;

    function dfs(x, y) {
        if (x < 0 || y < 0 || x >= row || y >= col || grid2[x][y] === 0) {
            return true;
        }
        if (grid1[x][y] === 0 && grid2[x][y] === 1) {
            return false;
        }
        grid2[x][y] = 0;
        let res = new Array(4).fill(true);
        res[0] = dfs(x - 1, y);
        res[1] = dfs(x, y - 1);
        res[2] = dfs(x + 1, y);
        res[3] = dfs(x, y + 1);
        return res[0] && res[1] && res[2] && res[3];
    }
};