20200408

Plan

leetcode 每日一题 面试题13. 机器人的运动范围

Notes

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1 输出：3

示例 2：

输入：m = 3, n = 1, k = 0 输出：1

解法： 一、这道题刚拿到的时候想法是遍历所有小于等于[m-1,n-1]的格子，把横纵坐标相加，然后判断是否小于等于k，但是这样有一个漏洞就是比如（10，0）这个坐标相加起来是1，当k>=1时都能满足，但是题中有一个条件是机器人每次只能上下左右走一步，它可能根本就不能到达(9,0)的位置，所以也到不了（10，0），故这种解法不可行。

二、后来又想，从第一列找到机器人能到达的最远处，是(0,k),那么第二列最远就是(1,k-1),第三列就是(2,k-2)...以此类推最后一列就是(k,0),所以最终答案就是1+2+3+...+n，然而这种情况只适用于k<=m的情况，如果k>m，那么第一列就可以到达(0,m)，第二列最远就不是(0,m-1),而可能更远，所以这种解法也不可行。

三、看了题解之后，恍然大悟，觉得自己是个弱智。 首先机器人从（0，0）开始出发，那么可以到达格子（i,j）的前提是可以达到(i-1,j)或者(i,j-1)。有了这个前提，就可以用一个二维数组canvisit表示整个坐标，初始化全为false，只有(0,0)初始化为true，表示可以到达，接着遍历整个坐标系，canvisit[i][j]=true当且仅当(canvisit[i-1][j]=true||canvisit[i][j-1]=true)&&sum(坐标i,坐标j)<=k，累加后返回结果即可

More

吐槽一下go的二维数组初始化,数组的长度必须是常量，变量不可以。如果想要用变量初始化的话只能用切片slice，切片的初始化又很麻烦，记录一下： canvisit := make([][]bool, m) for i := 0; i < m; i++ { canvisit[i] = make([]bool, n) }