leetcode算法题--找出最安全路径

原题链接：https://leetcode.cn/problems/find-the-safest-path-in-a-grid/description/

func maximumSafenessFactor(grid [][]int) int {n := len(grid)type pair struct {x inty int}p := make([]pair, 0)dis := make([][]int, n)for i := range dis {dis[i] = make([]int, n)for j := range dis[i] {if grid[i][j] == 1 {p = append(p, pair{i, j}) } else {dis[i][j] = -1}}}dirs := [][]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};groups := [][]pair{p}for len(p) != 0 {tmp := pp = make([]pair, 0) for _, pa := range tmp {for _, dir := range dirs {i, j := pa.x, pa.yx := i + dir[0] y := j + dir[1]if x >= 0 && x < n && y >= 0 && y < n && dis[x][y] < 0 {p = append(p, pair{x, y})dis[x][y] = len(groups)}} } groups = append(groups, p)}// 并查集m := n * n - 1 fa := make([]int, m + 1)for i := 0; i <= m; i ++ {fa[i] = i}var find func(x int) intfind = func(x int) int {if fa[x] != x {fa[x] = find(fa[x])}return fa[x]}nn := len(groups) for i := nn - 2; i > 0; i -- {pairs := groups[i] for _, pair := range pairs {for _, dir := range dirs {i, j := pair.x, pair.yx := i + dir[0] y := j + dir[1]if x >= 0 && x < n && y >= 0 && y < n && dis[x][y] >= dis[i][j] {fa[find(x*n+y)] = find(i*n+j)}} if find(0) == find(m) {return i }}} return 0 
}