-
Notifications
You must be signed in to change notification settings - Fork 514
/
d.go
41 lines (38 loc) · 797 Bytes
/
d.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package main
import "sort"
// github.com/EndlessCheng/codeforces-go
func maximumMinimumPath(a [][]int) (ans int) {
type pair struct{ x, y int }
dir4 := []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
n, m := len(a), len(a[0])
ans = sort.Search(min(a[0][0], a[n-1][m-1])+1, func(low int) bool {
vis := make([][]bool, n)
for i := range vis {
vis[i] = make([]bool, m)
}
var f func(int, int) bool
f = func(x, y int) bool {
if x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || a[x][y] < low {
return false
}
if x == n-1 && y == m-1 {
return true
}
vis[x][y] = true
for _, d := range dir4 {
if f(x+d.x, y+d.y) {
return true
}
}
return false
}
return !f(0, 0)
}) - 1
return
}
func min(a, b int) int {
if a < b {
return a
}
return b
}