岛屿数量

[Sunny-117]

No description provided.

[Nasuke]

并查集的做法

/**
 * @param {character[][]} grid
 * @return {number}
 */
class UnionSet {
    constructor(n) {
        this.fa = Array(n + 1)
        for (let i = 0; i < n; i++) {
            this.fa[i] = i
        }
    }
    get(x) {
        return this.fa[x] = (this.fa[x] == x ? x : this.get(this.fa[x]))
    }
    merge(a, b) {
        this.fa[this.get(b)] = this.get(a)
    }
}
var numIslands = function (grid) {
    let row = grid.length, col = grid[0].length, ans = 0
    let u = new UnionSet(row * col)

    function toIndex(a, b) {
        return a * col + b
    }
    // kp:构建row*col的网格
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (grid[i][j] == '0') continue
            //是1的并且不在边界的话找左上
            if (i > 0 && grid[i - 1][j] == '1') u.merge(toIndex(i, j), toIndex(i - 1, j))
            if (j > 0 && grid[i][j - 1] == '1') u.merge(toIndex(i, j), toIndex(i, j - 1))
        }
    }

    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (grid[i][j] == 1 && u.get(toIndex(i, j)) === toIndex(i, j)) ans++
        }
    }

    return ans
};

[Achetto]

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
  let dao = 0;
  let m = grid.length
  let n = grid[0].length;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] == 1) {
        dao++;
        infect(i,j);
      }
    }
  }
  function infect(i,j) {
    grid[i][j] = 2;
    if (i + 1 < m && grid[i + 1][j] == 1) infect(i + 1, j);
    if (i - 1 >= 0 && grid[i - 1][j] == 1) infect(i - 1, j);
    if (j + 1 < n && grid[i][j + 1] == 1) infect(i, j + 1);
    if (j - 1 >= 0 && grid[i][j - 1] == 1) infect(i, j - 1);
  }
  return dao;
};

[xiaodye]

leetcode-200，解法：DFS，递归

/**
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * @param grid
 * @returns
 */
export default function numIslands(grid: string[][]): number {
  const moveX = [0, 1, 0, -1];
  const moveY = [1, 0, -1, 0];

  if (grid.length === 0 || grid[0].length === 0) return 0;

  // 初始化岛屿数量，缓存二维数组的行数与列数
  let count = 0;
  const row = grid.length;
  const column = grid[0].length;

  const dfs = function (i: number, j: number) {
    // 如果试图探索的范围已经越界，则return
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === "0") return;

    grid[i][j] = "0";

    // 遍历完当前的1，继续去寻找下一个1，顺序为下右上左
    for (let k = 0; k < 4; k++) {
      dfs(i + moveX[k], j + moveY[k]);
    }
  };

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < column; j++) {
      if (grid[i][j] === "1") {
        dfs(i, j);
        count++;
      }
    }
  }

  return count;
}

// test
const grid = [
  ["1", "1", "1", "1", "0"],
  ["1", "1", "0", "1", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "0", "0", "1"],
];
console.log(numIslands(grid));

[jlx2002]

转化为求联通块的数量即可

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let n = grid.length, m = grid[0].length;
    let st = new Array(100010);
    st.fill(false);
    let dx = [0,0,1,-1],dy = [1,-1,0,0];
    function calc(i, j){
        return i * m + j;
    }
    // dfs 深搜所有1能连接的块
    function dfs(i, j){
        st[calc(i, j)] = true;
        for(let k = 0; k < 4; k ++){
            let  tx = dx[k] + i,ty= dy[k] + j;
             if (0 <= tx && tx < n && 0 <= ty && ty < m){
                 if(!st[calc(tx,ty)] && grid[tx][ty] == '1'){
                    dfs(tx, ty);
                 }
             } 
        }
    }
    let  res = 0;
    for(let i = 0;i < n; i ++){
        for(let j = 0; j < m; j++){
            if(!st[calc(i,j)] && grid[i][j] == '1'){
                    res += 1;
                    dfs(i, j);
            }
        }
    }
    return res
};

[veneno-o]

# dfs
function numIslands(grid): number {
    const [m, n] = [grid.length, grid[0].length];
    // init step
    const step = new Array(m);
    for (let i = 0; i < m; i++) {
        step[i] = (new Array(n).fill(false));
    }
    const dirs = [[1,0],[0,1],[-1,0],[0,-1]];

    // 岛屿数量
    let res = 0;
    const dfs = (i, j, step) => {
        if(i < 0 || j < 0 || i > m - 1 || j > n-1 ||grid[i][j] != '1' || step[i][j]) return;
        step[i][j] = true;
        for(const [x,y] of dirs){
            dfs(i+x,j+y,step);
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == '1' && !step[i][j]){
                dfs(i, j, step);
                res++;
            } 
        }
    }
    
    return res;
};

[zzyyhh22lx]

/**
 * dfs
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let sum = 0;
    grid[-1] = [];
    grid[grid.length] = [];
    for(let i = 0; i < grid.length; i++) {
        for(let j = 0; j < grid[0].length; j++) {
            if(grid[i][j] == '1') {
                grid[i][j] = 0;
                sum++;
                dfs(i, j);
            }
        }
    }
    return sum;

    function dfs(i, j) {
        if(grid[i-1][j] == '1') {
            grid[i-1][j] = 0;
            dfs(i-1, j);
        }
        if(grid[i][j-1] == '1') {
            grid[i][j-1] = 0;
            dfs(i, j-1);
        }
        if(grid[i+1][j] == '1') {
            grid[i+1][j] = 0;
            dfs(i+1, j);
        }
        if(grid[i][j+1] == '1') {
            grid[i][j+1] = 0;
            dfs(i, j+1);    
        }
    }
};

[xun-zi]

字符的0为真，导致出了问题

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    const n = grid.length, m = grid[0].length;
    function deleteIsland(x, y) {
        const dx = [-1, 0, 1, 0], dy = [0, 1, 0, -1];
        grid[x][y] = '0';
        for (let i = 0; i < 4; i++) {
            let x1 = dx[i] + x, y1 = dy[i] + y;
            if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && grid[x1][y1] == '1') deleteIsland(x1, y1);
        }
    }
    let count = 0;
    for (let i = 0; i < n; i++)
        for (let j = 0; j < m; j++)
            if (grid[i][j] == '1') {
                count++;
                deleteIsland(i, j);
            }
    return count;
};

[cscty]

var numIslands = function (grid) {
let row = grid.length;
let col = grid[0].length;
let used = new Array(row)
.fill(0)
.map(() => new Array(col).fill(0));
console.log(used);
let count = 0;
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
if (used[i][j] === 0 && grid[i][j] === "1") {
count++;
dfs(i, j);
}
}
}
function dfs(x, y) {
if (
x < 0 ||
x >= row ||
y < 0 ||
y >= col ||
grid[x][y] === "0" ||
used[x][y] === 1
)
return;
used[x][y] = 1;
let dire = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
];
dire.forEach((val) => dfs(x + val[0], y + val[1]));
}
return count;
};

[Simonduya]

function numIslands(grid) {
    let count = 0;

    function dfs(i, j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] === '0') return;
        grid[i][j] = '0';
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                dfs(i, j);
                count++;
            }
        }
    }

    return count;
}

[fengyxz]

var numIslands = function(grid) {
    let res = 0;
    const row = grid.length;
    const col = grid[0].length; 
    const dx = [1,-1,0,0];
    const dy = [0,0,1,-1];
    const dfs = (x,y) => {
        if(x<0 || x>=row)return; 
        if(y<0 || y>=col)return;
        if(grid[x][y] !== '1')return;
        else grid[x][y] = '-1';
        for(let i = 0;i < 4;i++){
            dfs(x+dx[i],y+dy[i]);
        }
    }
    for(let i = 0;i < row; i++){
        for(let j = 0;j < col; j++){
            if(grid[i][j] === '1'){
                dfs(i,j);
                res++;
            }
        }
    }
    return res;
};

[xianjianlf2]

const numIslands = (grid) => {
    let count = 0
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === "1") {
                count++
                dfs(grid, i, j)
            }
        }
    }
    return count
}


const dfs = (grid, x, y) => {
    if (!isInArea(grid, x, y)) return
    if (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)
}

const isInArea = (grid, x, y) => {
    return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length
}