778. Swim in Rising Water

Hard

Description

給定一個 n x n 的網格 grid，grid[i][j] 代表該位置的海拔。在時間 t 時，水位為 t，你可以游到任何海拔 <= t 的相鄰格子。回傳從左上角 (0,0) 游到右下角 (n-1,n-1) 所需的最小時間。

Example:

Input: grid = [[0,2],[1,3]] Output: 3

Intuition#

找一條從起點到終點的路徑，使路徑上的最大海拔最小化 – 變形的最短路徑問題。

不是求最短距離，而是求路徑上最大值的最小化（minimax path）
可以用修改版 Dijkstra：優先佇列按「路徑最大海拔」排序
也可以用二分搜尋 + BFS/DFS 驗證

Approaches#

1: 二分搜尋 + BFS#

概念: 二分搜尋答案 t，用 BFS 驗證在水位 t 時是否能從起點到終點
時間複雜度: O(n^2 log n)
空間複雜度: O(n^2)

class Solution {
    fun swimInWater(grid: Array<IntArray>): Int {
        val n = grid.size
        val dirs = intArrayOf(0, 1, 0, -1, 0)

        fun canReach(t: Int): Boolean {
            if (grid[0][0] > t) return false
            val visited = Array(n) { BooleanArray(n) }
            val queue: ArrayDeque<Int> = ArrayDeque()
            visited[0][0] = true
            queue.add(0)
            while (queue.isNotEmpty()) {
                val cur = queue.removeFirst()
                val r = cur / n
                val c = cur % n
                if (r == n - 1 && c == n - 1) return true
                for (d in 0 until 4) {
                    val nr = r + dirs[d]
                    val nc = c + dirs[d + 1]
                    if (nr in 0 until n && nc in 0 until n && !visited[nr][nc] && grid[nr][nc] <= t) {
                        visited[nr][nc] = true
                        queue.add(nr * n + nc)
                    }
                }
            }
            return false
        }

        var lo = grid[0][0]
        var hi = n * n - 1
        while (lo < hi) {
            val mid = (lo + hi) / 2
            if (canReach(mid)) hi = mid
            else lo = mid + 1
        }
        return lo
    }
}

⭐2: 修改版 Dijkstra（最小堆）#

概念: 用最小堆按「到達該格子需要的最小時間（路徑最大海拔）」排序，類似 Dijkstra
時間複雜度: O(n^2 log n)
空間複雜度: O(n^2)

class Solution {
    fun swimInWater(grid: Array<IntArray>): Int {
        val n = grid.size
        val dirs = intArrayOf(0, 1, 0, -1, 0)
        val visited = Array(n) { BooleanArray(n) }
        // [maxElevation, row, col]
        val pq = PriorityQueue<IntArray>(compareBy { it[0] })
        pq.add(intArrayOf(grid[0][0], 0, 0))
        visited[0][0] = true

        while (pq.isNotEmpty()) {
            val (t, r, c) = pq.poll()
            if (r == n - 1 && c == n - 1) return t
            for (d in 0 until 4) {
                val nr = r + dirs[d]
                val nc = c + dirs[d + 1]
                if (nr in 0 until n && nc in 0 until n && !visited[nr][nc]) {
                    visited[nr][nc] = true
                    pq.add(intArrayOf(maxOf(t, grid[nr][nc]), nr, nc))
                }
            }
        }
        return -1
    }
}

補充解法：Union-Find

概念: 按海拔從小到大排序所有格子，逐一開放並 union 相鄰已開放格子，直到起點和終點連通
時間複雜度: O(n^2 log n)
空間複雜度: O(n^2)

class Solution {
    private lateinit var parent: IntArray
    private lateinit var rank: IntArray

    fun swimInWater(grid: Array<IntArray>): Int {
        val n = grid.size
        parent = IntArray(n * n) { it }
        rank = IntArray(n * n)
        val dirs = intArrayOf(0, 1, 0, -1, 0)

        val cells = Array(n * n) { intArrayOf(0, 0) }
        for (i in 0 until n) {
            for (j in 0 until n) {
                cells[grid[i][j]] = intArrayOf(i, j)
            }
        }

        val opened = Array(n) { BooleanArray(n) }
        for (t in 0 until n * n) {
            val (r, c) = cells[t]
            opened[r][c] = true
            for (d in 0 until 4) {
                val nr = r + dirs[d]
                val nc = c + dirs[d + 1]
                if (nr in 0 until n && nc in 0 until n && opened[nr][nc]) {
                    union(r * n + c, nr * n + nc)
                }
            }
            if (find(0) == find(n * n - 1)) return t
        }
        return n * n - 1
    }

    private fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x])
        return parent[x]
    }

    private fun union(x: Int, y: Int) {
        val px = find(x)
        val py = find(y)
        if (px == py) return
        if (rank[px] < rank[py]) parent[px] = py
        else if (rank[px] > rank[py]) parent[py] = px
        else { parent[py] = px; rank[px]++ }
    }
}

🔑 Takeaways#

Pattern: Minimax 路徑 – 最小化路徑上的最大值，修改版 Dijkstra
關鍵技巧: Dijkstra 的鬆弛條件改為 maxOf(t, grid[nr][nc])；二分搜尋 + 可達性驗證也是經典套路