leetcode_lcp45_go_自行车炫技赛场

题目

「力扣挑战赛」中 N*M 大小的自行车炫技赛场的场地由一片连绵起伏的上下坡组成，

场地的高度值记录于二维数组 terrain 中，场地的减速值记录于二维数组 obstacle 中。

若选手骑着自行车从高度为 h1 且减速值为 o1 的位置到高度为 h2 且减速值为 o2 的相邻位置（上下左右四个方向），

速度变化值为 h1-h2-o2（负值减速，正值增速）。

选手初始位于坐标 position 处且初始速度为 1，请问选手可以刚好到其他哪些位置时速度依旧为 1。

请以二维数组形式返回这些位置。若有多个位置则按行坐标升序排列，若有多个位置行坐标相同则按列坐标升序排列。

注意：骑行过程中速度不能为零或负值

示例 1：输入：position = [0,0], terrain = [[0,0],[0,0]], obstacle = [[0,0],[0,0]] 输出：[[0,1],[1,0],[1,1]]

解释：由于当前场地属于平地，根据上面的规则，选手从[0,0]的位置出发都能刚好在其他处的位置速度为 1。

示例 2：输入：position = [1,1], terrain = [[5,0],[0,6]], obstacle = [[0,6],[7,0]] 输出：[[0,1]]

解释：选手从 [1,1] 处的位置出发，到 [0,1] 处的位置时恰好速度为 1。

提示：n == terrain.length == obstacle.length

m == terrain[i].length == obstacle[i].length

1 <= n <= 100

1 <= m <= 100

0 <= terrain[i][j], obstacle[i][j] <= 100

position.length == 2

0 <= position[0] < n

0 <= position[1] < m

解题思路分析

1、深度优先搜索；时间复杂度O(n^2)，空间复杂度O(n^2)

var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}
var res [][]int
var visited map[[3]int]bool
var n, m int
var originX, originY int

func bicycleYard(position []int, terrain [][]int, obstacle [][]int) [][]int {
   res = make([][]int, 0)
   n, m = len(terrain), len(terrain[0])
   originX, originY = position[0], position[1]
   visited = make(map[[3]int]bool)
   visited[[3]int{originX, originY, 1}] = true
   dfs(terrain, obstacle, originX, originY, 1)
   sort.Slice(res, func(i, j int) bool {
      if res[i][0] == res[j][0] {
         return res[i][1] < res[j][1]
      }
      return res[i][0] < res[j][0]
   })
   return res
}

func dfs(terrain [][]int, obstacle [][]int, i, j int, speed int) {
   if speed == 1 && (i == originX && j == originY) == false {
      res = append(res, []int{i, j})
   }
   for k := 0; k < 4; k++ {
      x, y := i+dx[k], j+dy[k]
      if 0 <= x && x < n && 0 <= y && y < m {
         // next = speed + h1-h2-o2
         next := speed + (terrain[i][j] - terrain[x][y] - obstacle[x][y])
         if next > 0 && visited[[3]int{x, y, next}] == false {
            visited[[3]int{x, y, next}] = true
            dfs(terrain, obstacle, x, y, next)
         }
      }
   }
}

2、广度优先搜索；时间复杂度O(n^2)，空间复杂度O(n^2)

var dx = []int{0, 1, 0, -1}
var dy = []int{1, 0, -1, 0}

func bicycleYard(position []int, terrain [][]int, obstacle [][]int) [][]int {
   res := make([][]int, 0)
   n, m := len(terrain), len(terrain[0])
   originX, originY := position[0], position[1]
   visited := make(map[[3]int]bool)
   visited[[3]int{originX, originY, 1}] = true
   queue := make([][3]int, 0)
   queue = append(queue, [3]int{originX, originY, 1})
   for len(queue) > 0 {
      node := queue[0]
      queue = queue[1:]
      i, j, speed := node[0], node[1], node[2]
      if speed == 1 && (i == originX && j == originY) == false {
         res = append(res, []int{i, j})
      }
      for k := 0; k < 4; k++ {
         x, y := i+dx[k], j+dy[k]
         if 0 <= x && x < n && 0 <= y && y < m {
            // next = speed + h1-h2-o2
            next := speed + (terrain[i][j] - terrain[x][y] - obstacle[x][y])
            if next > 0 && visited[[3]int{x, y, next}] == false {
               visited[[3]int{x, y, next}] = true
               queue = append(queue, [3]int{x, y, next})
            }
         }
      }
   }
   sort.Slice(res, func(i, j int) bool {
      if res[i][0] == res[j][0] {
         return res[i][1] < res[j][1]
      }
      return res[i][0] < res[j][0]
   })
   return res
}