一、题目
地上有一个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。请问该机器人能够到达多少个格子？
二、示例
2.1> 示例 1：
【输入】m = 2, n = 3, k = 1
【输出】3
2.2> 示例 2：
【输入】m = 3, n = 1, k = 0
【输出】1
提示：
1<= n,m <=1000<= k <=20
三、解题思路
- 根据题目描述，我们需要在
m行n列的矩阵中寻找行坐标和列坐标的数位之和不大于k的格子数量。那么我们需要做到如下几个步骤：
【步骤1】提供计算
行坐标和列坐标数位之和的函数方法。【步骤2】执行
深度优先算法或广度优先算法，对比每个盒子数位之和是否满足不大于k。【步骤3】我们要采用某种方式，可以
防止重复遍历。
- 确定了具体的解题步骤，我们首先来看如何计算一个数字的数位之和。常用的方式是，通过与10取余（
%10）的方式来获得最后一位的数字，那么获取到个位之后，再通过与10取整（/10）的方式来移除最后一位，那么再次通过与10取余计算后，就取得了原数字的十位数字了，依次类推，直至所有数字的位数都截取出来。并且在每次获取最后一位的操作过程中，都进行加合计算，最终的结果就是某个数字的数位之和了。具体操作，如下图所示：
- 那么上面我们解决了
步骤1的函数算法，下面我们选取深度优先来对矩阵中的每个格子执行遍历操作。在遍历过程中，由于我们是从[0,0]这个格子开始遍历的，它是所有格子数位合的最小值（即：0+0=0），那么对于深度遍历的方向来说，我们不需要考虑会使整个数位和变小的情况（即：向上遍历（row-1）和向左遍历（col-1）），只需要考虑向下遍历（row+1）和向右遍历（col+1）这两种行走路径。那么，我们再整理一下如下几个结束遍历的条件：
【路径结束条件1】row >= m 或者 col >= n；
【路径结束条件2】格子数位之和大于k；
【路径结束条件3】待行走的格子已经被走过了。
- 针对“
路径结束条件3”，我们可以采用二维数组或者哈希表的方式，记录走过的格子即可。下面是以输入：m = 4, n = 6, k = 5为例，具体演示了处理流程。请见下图所示：
四、代码实现
classSolution { boolean[][] mark; publicintmovingCount(intm, intn, intk) { mark=newboolean[m][n]; returndfs(0, 0, m, n, k); } intdfs(introw, intcol, intm, intn, intk) { if (row>=m||col>=n||mark[row][col] ||sum(row) +sum(col) >k) return0; mark[row][col] =true; return1+dfs(row+1, col, m, n, k) +dfs(row, col+1, m, n, k); } intsum(intx) { ints=0; while(x!=0) { s+=x%10; x=x/10; } returns; } }
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」
