一、题目

地上有一个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 <= 100 <= 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(int m,int n,int k){mark =newboolean[m][n];return dfs(,, m, n, k);}intdfs(int row,int col,int m,int n,int k){if(row >= m || col >= n || mark[row][col]|| sum(row)+ sum(col)>k)return;mark[row][col]=true;return1+ dfs(row+1, col, m, n, k)+ dfs(row, col+1, m, n, k);}intsum(int x){ints=;while(x !=){s += x %10;x = x /10;}return s;}}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」