[数据结构与算法]golang力扣leetcode 1765.地图中的最高点

1765.地图中的最高点

1765.地图中的最高点

题解

看到题目立马想到BFS，模板水题

代码

package main

type pair struct {
	i, j int
}

var dis = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func highestPeak(isWater [][]int) [][]int {
	queue := make([]pair, 0)
	result := make([][]int, len(isWater))
	for i, val1 := range isWater {
		result[i] = make([]int, len(val1))
		for j, val2 := range val1 {
			if val2 == 0 {
				result[i][j] = -1
			} else {
				result[i][j] = 0
				queue = append(queue, pair{i, j})
			}
		}
	}
	for len(queue) > 0 {
		now := queue[0]
		queue = queue[1:]
		for _, step := range dis {
			nextI, nextJ := now.i+step.i, now.j+step.j
			if nextI >= 0 && nextI < len(isWater) &&
				nextJ >= 0 && nextJ < len(isWater[0]) && result[nextI][nextJ] == -1 {
				result[nextI][nextJ] = result[now.i][now.j] + 1
				queue = append(queue, pair{nextI, nextJ})
			}
		}
	}
	return result
}