778. Swim in Rising Water

Problem

On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Example 1:

Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Note:

1. 2 <= N <= 50.
2. grid[i][j] is a permutation of [0, ..., N*N - 1].

Problem Summary

In an N x N coordinate grid grid, the value of each square grid[i][j] represents the platform elevation at position (i,j). Now it starts to rain. At time t, the water level at any position in the pool is t. You can swim from one platform to any of its four adjacent platforms, but the premise is that the water level at this time must submerge both platforms simultaneously. Assume that you can move an infinite distance instantly, that is, swimming inside the grid takes no time by default. Of course, while swimming you must stay inside the coordinate grid.

You start from the top-left platform (0, 0) of the coordinate grid. What is the minimum time needed for you to reach the bottom-right platform (N-1, N-1) of the coordinate grid?

Hints:

• 2 <= N <= 50.
• grid[i][j] lies within the interval [0, ..., N*N - 1].

Solution Ideas

• Given a grid[i][j] grid, each cell represents the height of a platform in the swimming pool. At time t, the water height in the swimming pool is t. You can swim across only after the water height reaches the platform's height. Ask, starting from (0,0), what is the shortest time needed to reach (N-1, N-1).
• There are multiple solutions to this problem. The first solution idea is to use DFS + binary search. DFS is used to traverse and determine whether the destination is reachable. Use time (that is, the current height flooded by water) to determine whether the endpoint (N-1, N-1) can be reached. Binary search is used to search for the final result time. Why consider using binary search for acceleration? The reason is: time increases sequentially from 0 to max. max is the height of the highest platform in the swimming pool. When time increases from 0 to max, the endpoint (N-1, N-1) can definitely be reached, because the water is higher than all platforms. If we want to quickly find a time t that makes point (0,0) connected to point (N-1, N-1), then binary search comes to mind for acceleration. The condition for deciding whether to take the middle value is whether point (0,0) and point (N-1, N-1) are connected.
• The second solution idea is Union-Find. As long as point (0,0) and point (N-1, N-1) are not connected, meaning the destination cannot be reached by swimming, start performing union() operations. Since the starting point is (0,0), try toward the right i + 1 and downward j + 1. After each round of attempts, time increases by 1 second, that is, the height increases by one. Until point (0,0) and point (N-1, N-1) are just connected, this point in time is the final required answer.

Code

package leetcode

import (
	"github.com/halfrost/leetcode-go/template"
)

// Solution 1 DFS + Binary Search
func swimInWater(grid [][]int) int {
	row, col, flags, minWait, maxWait := len(grid), len(grid[0]), make([][]int, len(grid)), 0, 0
	for i, row := range grid {
		flags[i] = make([]int, len(row))
		for j := 0; j < col; j++ {
			flags[i][j] = -1
			if row[j] > maxWait {
				maxWait = row[j]
			}
		}
	}
	for minWait < maxWait {
		midWait := (minWait + maxWait) / 2
		addFlags(grid, flags, midWait, 0, 0)
		if flags[row-1][col-1] == midWait {
			maxWait = midWait
		} else {
			minWait = midWait + 1
		}
	}
	return minWait
}

func addFlags(grid [][]int, flags [][]int, flag int, row int, col int) {
	if row < 0 || col < 0 || row >= len(grid) || col >= len(grid[0]) {
		return
	}
	if grid[row][col] > flag || flags[row][col] == flag {
		return
	}
	flags[row][col] = flag
	addFlags(grid, flags, flag, row-1, col)
	addFlags(grid, flags, flag, row+1, col)
	addFlags(grid, flags, flag, row, col-1)
	addFlags(grid, flags, flag, row, col+1)
}

// Solution 2 Union-Find (not the optimal solution for this problem)
func swimInWater1(grid [][]int) int {
	n, uf, res := len(grid), template.UnionFind{}, 0
	uf.Init(n * n)
	for uf.Find(0) != uf.Find(n*n-1) {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if grid[i][j] > res {
					continue
				}
				if i < n-1 && grid[i+1][j] <= res {
					uf.Union(i*n+j, i*n+j+n)
				}
				if j < n-1 && grid[i][j+1] <= res {
					uf.Union(i*n+j, i*n+j+1)
				}
			}
		}
		res++
	}
	return res - 1
}