200. 岛屿数量（算法200-82）

const dfs = function (grid, x, y, col, row) {
    if (x < 0 || x >= col || y < 0  || y >= row || grid[x][y] === '0') {
        return
    }
    grid[x][y] = '0'
    dfs(grid, x + 1, y, col, row)
    dfs(grid, x - 1, y, col, row)
    dfs(grid, x, y + 1, col, row)
    dfs(grid, x, y - 1, col, row)
}
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
    if (!grid || !grid.length) return 0
    const row = grid.length,
        col = grid[0].length
    let result = 0
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (grid[i][j] === '1') {
                result += 1
                dfs(grid, i, j, row, col)
            }
        }
    }
    return result
};

var numIslands = function (grid) {
    if (!grid || !grid.length) return 0
    const row = grid.length,
        col = grid[0].length,
        queue = []
    let result = 0
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (grid[i][j] === '1') {
                result += 1
                queue.push([i, j])
                grid[i][j] = '0'
                while (queue.length) {
                    const [x, y] = queue.shift()
                    if (x - 1 >= 0 && grid[x - 1][y] === '1') {
                        grid[x - 1][y] = '0'
                        queue.push([x - 1, y])
                    }
                    if (x + 1 < row && grid[x + 1][y] === '1') {
                        grid[x + 1][y] = '0'
                        queue.push([x + 1, y])
                    }
                    if (y - 1 >= 0 && grid[x][y - 1] === '1') {
                        grid[x][y - 1] = '0'
                        queue.push([x, y - 1])
                    }
                    if (y + 1 < col && grid[x][y + 1] === '1') {
                        grid[x][y + 1] = '0'
                        queue.push([x, y + 1])
                    }
                }
            }
        }
    }
    return result
};

var numIslands = function (grid) {
    if (!grid || !grid.length) return 0
    const row = grid.length,
        col = grid[0].length
    let water = 0
    const uf = new UnionFind(grid)
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if(grid[i][j] === '0') {
                water++
            } else {
                const directions = [[0,1], [0, -1], [1, 0], [-1, 0]]
                for(let k of directions) {
                    const x = i + k[0]
                    const y = j + k[1]
                    if(x >=0 && y >= 0 && x < row && y < col && grid[x][y] === '1') {
                        uf.union(x * col + y, i * col + j)
                    }
                }
            }
        }
    }
    return uf.getCount() - water
};
class UnionFind {
    root = null
    count = 0
    constructor(grid) {
        const row = grid.length
        const col = grid[0].length
        this.count = row * col
        this.root = new Array(this.count)
        for(let i = 0; i < this.count; i++) {
            this.root[i] = i
        }
    }
    find(x) {
        if(x === this.root[x]) return x
        return this.root[x] = this.find(this.root[x])
    }
    union(x, y) {
        const rootX = this.find(x)
        const rootY = this.find(y)
        if(rootX !== rootY) {
            this.root[rootX] = rootY
            this.count--
        }
    }
    getCount() {
        return this.count
    }
}