Heapify push

今日練習的題目是 778. Swim in Rising Water，解法似乎有許多種，我自己用的是 Priority Queue，雖然不是相對有效的方法，不過在 C++/Go/Rust 都還可以跑到 Runtime 0ms Beats 100%，這篇算是補充之前的 Heapify 沒有提到的 push 的使用方式。

如果是使用 Python3 的話，因為預設是 Min Heap，剛好是解題需要的，所以不用花點小心思來轉換。

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        visited = [[False for _ in range(n)] for _ in range(m)]
        heap = []
        heapq.heappush(heap, (grid[0][0], 0, 0))
        visited[0][0] = True
        d = (0, 1, 0, -1, 0)
        while heap:
            h, x, y = heapq.heappop(heap)
            if x == m - 1 and y == n - 1:
                return h
            for i in range(4):
                nx = x + d[i]
                ny = y + d[i + 1]
                if nx < 0 or nx >= m or ny < 0 or ny >= n or visited[nx][ny]:
                    continue
                heapq.heappush(heap, (max(h, grid[nx][ny]), nx, ny))
                visited[nx][ny] = True
        return 0

如果是使用 C++ 的話，因為預設是 Max Heap，所以需要花點小心思來轉換。

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        priority_queue<tuple<int, int, int>> pq;
        pq.push({-grid[0][0], 0, 0});
        array<int, 5> d{0, 1, 0, -1, 0};
        vector< vector < bool > > visited(m, vector<bool>(n));
        visited[0][0] = true;
        while (!pq.empty()) {
            auto [cur, x, y] = pq.top();
            if (x == m - 1 && y == n - 1)
                return -cur;
            pq.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = x + d[i];
                int ny = y + d[i + 1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny])
                    continue;
                visited[nx][ny] = true;
                pq.push({min(cur, -grid[nx][ny]), nx, ny});
            }
        }
        return 0;
    }
};

如果是使用 Go 的話，又要很麻煩地自己多刻一些程式碼來搭配 container/heap 使用。

import "container/heap"

type PriorityQueue [][]int

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i][0] < pq[j][0] }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x any) {
	*pq = append(*pq, x.([]int))
}
func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[0 : n-1]
	return x
}

func swimInWater(grid [][]int) int {
	d := []int{0, 1, 0, -1, 0}
	m, n := len(grid), len(grid[0])
	visited := make([][]bool, m)
	for i := range m {
		visited[i] = make([]bool, n)
	}
	pq := PriorityQueue([][]int{})
	heap.Push(&pq, []int{grid[0][0], 0, 0})
	visited[0][0] = true
	for pq.Len() != 0 {
		arr := heap.Pop(&pq).([]int)
		h, x, y := arr[0], arr[1], arr[2]
		if x == m-1 && y == n-1 {
			return h
		}
		for i := range 4 {
			nx := x + d[i]
			ny := y + d[i+1]
			if nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny] {
				continue
			}
			heap.Push(&pq, []int{max(h, grid[nx][ny]), nx, ny})
			visited[nx][ny] = true
		}
	}
	return 0
}

如果是使用 Rust 的話，就需要使用到 std::collections::BinaryHeap，預設是 Max Heap 所以要花點小心思來轉換，不過搭配 `while let Some(...) = pq.pop()` 整個行雲流水般好用。

use std::collections::BinaryHeap;

impl Solution {
    pub fn swim_in_water(grid: Vec < Vec < i32 > >) -> i32 {
        let d = [0, 1, 0, -1, 0];
        let m = grid.len();
        let n = grid[0].len();
        let mut pq = BinaryHeap::new();
        let mut visited = vec![vec![false; n]; m];
        pq.push((-grid[0][0], 0, 0));
        visited[0][0] = true;
        while let Some((h, x, y)) = pq.pop() {
            if x == m - 1 && y == n - 1 {
                return -h;
            }
            for i in 0..4 {
                let nx = x as i32 + d[i];
                let ny = y as i32 + d[i+1];
                if nx < 0 || ny < 0 || nx >= m as i32 || ny >= n as i32 {
                    continue;
                }
                let nx = nx as usize;
                let ny = ny as usize;
                if visited[nx][ny] {
                    continue;
                }
                pq.push((-grid[nx][ny].max(-h), nx, ny));
                visited[nx][ny] = true;
            }
        }
        0
    }
}