2020-04-08 leetcode 机器人的运动范围

解

最先想到的是暴力法
一时暴力一直爽，一直暴力一直爽！ --佚名

func movingCount(m int, n int, k int) int {
  flag := make([][]int, m)
  for i := 0; i < m; i++ {
    flag[i] = make([]int, n)
  }
  flag[0][0] = 1
  var r int
  var mark = n
  for i := 0;i< m ;i++{
    stepI :=getStep(i)
    for j:= 0;j<mark;j++{
      if i-1>=0 && flag[i-1][j] == 1 ||(j-1>=0 && flag[i][j-1] == 1){
        step := getStep(j)
        step += stepI
        if step <=k{
          r +=1
          flag[i][j]=1
        }
      }

    }
  }
  return r+1
}
func getStep(x int)int  {
  var r int
  if x >= 10{
    r = x/10+x%10
  }else{
    r=x
  }
  return r

• 小问题：需要记录上次遍历的位置，就是使视图遍历连贯
• 最有+1是个小细节

之后产生了深度优先的想法，不过始终觉的递归反人类

func movingCount2(m int, n int, k int) int {
  var count int
  var find [][]bool
  for i:=0;i<m;i++{
    var list = make([]bool,0)
    for j:=0;j<n;j++{
      list = append(list,false)
    }
    find = append(find,list)
  }
  // 查询
  DFS(0,0,&count,k,m,n,find)
  return count
}

func DFS(x int,y int,count *int,k int,m int,n int,find [][]bool){
  if x < 0 || y < 0 || x >= m || y >= n {
    return
  }
  if getStep(x)+getStep(y) <= k && find[x][y] == false{
    *count++
    find[x][y]=true
    DFS(x+1,y,count,k,m,n,find)
    DFS(x,y+1,count,k,m,n,find)
  }
}

• 其中可以省略向下和向右的遍历

小结

• 因为题目本身长度限制，及时使用暴力也是双百
• 上述两种方法都是双百

引用：

• leetcode ：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

认真工作，好好学习！