53 | 面试题：岛屿的个数

200. 岛屿数量

解法一：染色 FloodFill

写一个循环，遍历所有的节点，是1（陆地）的话，将count++，同时节点和附近节点都变成0（染色），依次递归。

实现方式：

1. DFS：对任意一个为1的节点，上下左右递归扩散，将周围的1改为0。
2. BFS：将 queue 放去队列，相邻的节点也放入 queue，把 queue 中的元素都变成0.

Kotlin 版（ DFS ）：
代码中有很多可优化的地方，如：可使用 String 替换 Pair、精简重复的定义等，这里是为了方便理解。

可解释的地方：

1. dx，dy 用于动态变换坐标
2. isValid用于判断是否越界以及忽略为‘0’的元素和访问过的元素

class Solution {
    lateinit var grid: Array<CharArray>
    val visited = HashSet<Pair<Int, Int>>()
    val dx = intArrayOf(-1, 1, 0, 0)
    val dy = intArrayOf(0, 0, -1, 1)

    fun numIslands(grid: Array<CharArray>): Int {
        if (grid.isNullOrEmpty()) return 0
        if (grid[0].isEmpty()) return 0
        val maxX = grid.size
        val maxY = grid[0].size
        this.grid = grid

        var sum = 0
        for (i in 0 until maxX) {
            for (j in 0 until maxY) {
                sum += floodfill_DFS(i, j)
            }
        }
        return sum
    }

    private fun floodfill_DFS(x: Int, y: Int): Int {
        return when {
            isValid(x, y) -> {
                visited.add(Pair(x, y))
                for (k in 0 until 4) {
                    floodfill_DFS(x + dx[k], y + dy[k])
                }
                1
            }
            else -> {
                0
            }
        }
    }

    private fun isValid(x: Int, y: Int): Boolean {
        val maxX = grid.size
        val maxY = grid[0].size
        if (x < 0 || x >= maxX || y < 0 || y >= maxY) return false
        if (grid[x][y] == '0' || Pair(x, y) in visited) return false
        return true
    }

}

Kotlin（BFS）版：这里就只贴 BFS 代码块了，其余部分除调用 floodfill_DFS 改为 floodfill_BFS 外并无不同。

private fun floodfill_BFS(x: Int, y: Int): Int {
    if (!isValid(x, y)) {
        return 0
    } else {
        val element = Pair(x, y)
        visited.add(element)
        val queue = ArrayDeque<Pair<Int, Int>>()
        queue.add(element)

        while (queue.isNotEmpty()) {
            val (curX, curY) = queue.pollFirst()
            for (k in 0 until 4) {
                val newX = curX + dx[k]
                val newY = curY + dy[k]
                if (isValid(newX, newY)) {
                    val pair = Pair(newX, newY)
                    visited.add(pair)
                    queue.add(pair)
                }
            }
        }
        return 1
    }

}

解法二：并查集

1. 把每个为1的元素，将其 parent 赋值为它自己。遍历所有的节点，相邻则合并。
2. 遍历查询有多少个 root 即可，此处可合并至上一步中。

Kotlin 版：rank 是一个高度数组，是一种按秩合并的加速手段

class Solution {

    fun numIslands(grid: Array<CharArray>): Int {
        if (grid.isNullOrEmpty()) return 0
        if (grid[0].isEmpty()) return 0

        val m = grid.size
        val n = grid[0].size

        val direction = arrayOf(Pair(0, 1), Pair(0, -1), Pair(-1, 0), Pair(1, 0))

        val uf = UnionFind(grid)

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid[i][j] == '0') continue
                direction.forEach { (dx, dy) ->
                    val ni = i + dx
                    val nj = j + dy
                    if (ni >= 0 && nj >= 0 && ni < m && nj < n && grid[ni][nj] == '1') {
                        //坐标合法，合并
                        //i * n + j 之前的节点 二维转一维
                        //ni * n + nj 不同方向的新节点 二维转一维
                        uf.union(i * n + j, ni * n + nj)
                    }
                }
            }
        }
        return uf.count
    }

    class UnionFind(grid: Array<CharArray>) {

        val m = grid.size
        val n = grid[0].size
        var count = 0
        val parent = IntArray(m * n) { -1 }
        val rank = IntArray(m * n) { 0 }

        init {
            for (i in 0 until m)
                for (j in 0 until n ){
                    if (grid[i][j]=='1'){
                        parent[i*n +j]=i*n +j
                        count++
                    }
                }
        }

        fun findRoot(i: Int): Int {
            if (parent[i]!=i){
                parent[i]=findRoot(parent[i])
            }
            return parent[i]
        }

        fun union(p: Int, q: Int) {
            val rootP = findRoot(p)
            val rootQ = findRoot(q)

            if (rootP!=rootQ){
                when {
                    rank[rootP]>rank[rootQ] -> {
                        parent[rootQ]=rootP
                    }
                    rank[rootP]>rank[rootQ] -> {
                        parent[rootP]=rootQ
                    }
                    else -> {
                        parent[rootQ]=rootP
                        rank[rootP]++
                    }
                }
                count--
            }
        }

    }

}