最近碰到一道有意思的求制高点的题：
/*
现在，有一个矩阵，矩阵的每个值代表山的高度（均大于1），现在要求找到这个山的所有制高点。
制高点指的是通过这个点可以从上下左右四个边界走出去这个矩阵平面，注意，是四个边界都能走出去。
在整个平面的移动规则是从一个点只可以向上下左右四个方向走，并且只能走到不大于自己的值的位置上去
matrix = [][]int{
[]int{1,3,2,3,5},
[]int{3,4,5,6,3},
[]int{2,7,4,3,3},
[]int{5,2,2,3,1},
}
expect := [][]int{
[]int{1,2},
[]int{1,3},
[]int{2,1},
}
*/
LeetCode中没有找到原题，我的第一反应是图的深度遍历，但是时间复杂度会比较高，另一种思路是用广度遍历进行反向推理。
今天用golang写了一上午碰到不少坑，很多低层方法需要自己实现，比如求交集，判断包含元素等，而且因为没有集合这种类型，用hash表存储的时候必须将一对数组转成string以后作为key存储，相比python的实现代码量还是挺多的。
package main
import (
"fmt"
)
func solution(matrix [][]int) [][]int {
ans := [][]int{}
m := len(matrix)
if m == 0 {
return ans
}
n := len(matrix[0])
topIn := [][]int{}
bottomIn := [][]int{}
leftIn := [][]int{}
rightIn := [][]int{}
for i := 0; i < m; i++ {
leftIn = append(leftIn, []int{i, 0})
rightIn = append(rightIn, []int{i, n - 1})
}
for j := 0; j < n; j++ {
topIn = append(topIn, []int{0, j})
bottomIn = append(bottomIn, []int{m - 1, j})
}
leftIn = bfs(leftIn, m, n, matrix)
rightIn = bfs(rightIn, m, n, matrix)
topIn = bfs(topIn, m, n, matrix)
bottomIn = bfs(bottomIn, m, n, matrix)
return interaction(bottomIn, interaction(topIn, interaction(leftIn, rightIn)))
}
func bfs(path [][]int, m, n int, matrix [][]int) [][]int {
curPath := path[:]
dirs := [][]int{
[]int{0, 1},
[]int{0, -1},
[]int{1, 0},
[]int{-1, 0},
}
for len(curPath) > 0 {
row, col := curPath[0][0], curPath[0][1]
curPath = curPath[1:]
for _, dir := range dirs {
newRow, newCol := row+dir[0], col+dir[1]
if newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && matrix[newRow][newCol] >= matrix[row][col] {
if !contains(path, []int{newRow, newCol}) {
path = append(path, []int{newRow, newCol})
curPath = append(curPath, []int{newRow, newCol})
}
}
}
}
return path
}
func contains(locs [][]int, target []int) bool {
for _, loc := range locs {
if loc[0] == target[0] && loc[1] == target[1] {
return true
}
}
return false
}
func interaction(locs1, locs2 [][]int) [][]int {
mp := map[string]int{}
ans := [][]int{}
for _, loc := range locs1 {
key := string(loc[0]) + string(loc[1])
mp[key]++
}
for _, loc := range locs2 {
key := string(loc[0]) + string(loc[1])
mp[key]++
}
for key, count := range mp {
if count > 1 {
row := int(key[0])
col := int(key[1])
ans = append(ans, []int{row, col})
}
}
return ans
}
func main() {
matrix := [][]int{
[]int{1, 3, 2, 3, 5},
[]int{3, 4, 5, 6, 3},
[]int{2, 7, 4, 3, 3},
[]int{5, 2, 2, 3, 1},
}
fmt.Println(solution(matrix))
}