本文转载自微信公众号《神奇程序员K》，作者：神奇程序员K，转载请联系神奇程序员K公众号。序中有矩阵。机器人可以从坐标网格(0,0)开始移动。每次可以左、右、上、下移动一格，但不能进入行坐标和列坐标的位数之和大于K的格子。机器人总共可以行走和它的轨迹。本文将与您分享解决此问题的方法。欢迎所有感兴趣的开发者阅读本文。实现思路在上一篇关于在矩阵中寻找路径的文章中，我们学习了使用回溯算法访问矩阵中的网格。本文要讨论的问题是在访问网格之前进行判断。满足条件就可以进入，不满足就不能进入。我们要做的判断层次是：计算要访问的格子坐标的位数之和，如果大于K（最大活动范围），则不能访问。位数之和：取出数中各位置的值相加的结果。例子：19的数字之和为1+9=10判断当前格子是否已经走过首先，我们需要创建一个与原矩阵大小相同的矩阵来判断机器人是否走过这个格子。js中无法直接创建指定大小的二维数组。创建思路如下：创建一个以矩阵的长度为size的数组并遍历创建的数组，然后创建一个以矩阵的第0个数组的长度为size的数组，赋值给遍历到每一个项目。判断网格是否可访问在访问网格时，我们需要判断要访问的网格是否可以进入。我们需要计算行坐标和列坐标的位数之和，然后将它们相加，判断相加的结果是否大于机器人。最大运动范围(K)。计算数字和的方法有两种：将数字转换成字符串，遍历取出每个字符，转换成数字，然后相加对数字进行取模运算，将结果相加，然后对数字本身进行/10操作，直到数字小于等于0开始移动机器人，我们需要7个参数：矩阵的总行数矩阵的总列数行坐标即将进入网格列坐标的网格的最大活动范围访问单位矩阵路径矩阵首先，我们需要判断边界条件（递归终止条件）。如果满足条件，则表示无法访问网格，可走网格为0（直接返回0）：要访问的网格的行坐标大于矩阵的总行数。待访问网格的行坐标小于0待访问网格的列坐标大于矩阵的总列数待访问网格的列坐标小于0当前网格有被访问过且不能进入当前格子如果满足以上条件，则表示当前格子可以访问，将当前格子中的值保存到action轨迹中，将当前格子标记为已访问状态，走过的格子数+1，递归尝试当前格子的其他四个方向的格子是否可以进入。当递归栈清空后，我们也得到了机器人可以进入的格子总数和它的轨迹。实现代码接下来，我们将上述思路转化为TypeScript代码。格子是否可以进入函数先来看判断当前格子是否可以进入的函数的实现，如下：/***判断机器人是否可以进入目标格子*@paramrow行坐标*@paramcol列coordinates*@paramtargetcriticalpoint*@private*/privatecheckPath(row:number,col:number,target:number):boolean{//两个坐标的位数之和必须小于等于临界点returnsumOfDigits(row)+sumOfDigits(col)<=target;}//转字符串实现exportfunctionsumOfDigits(target:number):number{letfinalVal=0;constcomputeVal=target.toString();for(leti=0;i0){finalVal+=Math.floor(target%10);target/=10;}returnfinalVal;}移动机器人函数，将机器人移动到指定格子。实现代码如下：/***开始移动机器人*@paramrows矩阵总行数*@paramcols矩阵总列数*@paramrow入格行坐标*@paramcol入格列坐标*@paramthreshold最大活动range*@paramisVisited访问标识矩阵*@parammatrix路径矩阵*@private*/rivatestartMoving(rows:number,cols:number,row:number,col:number,threshold:number,isVisited:Array>,matrix:Array>):number{//边界条件判断if(row>=rows||row<0||col>=cols||col<0||isVisited[row][col]||!this.checkPath(row,col,threshold)){return0;}//记录当前访问gridcontentthis.path+=`${matrix[row][col]}->`;//标记当前grid被访问过isVisited[row][col]=true;//grid访问次数+1return(1+this.startMoving(rows,cols,row+1,col,threshold,isVisited,matrix)+this.startMoving(rows,cols,row,col+1,threshold,isVisited,matrix)+this.startMoving(rows,cols,row-1,col,threshold,isVisited,matrix)+this.startMoving(rows,cols,row,col-1,threshold,isVisited,matrix));}Main函数最后我们来看一下实现main函数，如下Show:/***Title:*地面上有一个m行n列的格子*一个机器人从坐标为(0,0)的格子开始移动，*可以移动一个格子每次向左、向右、向上、向下移动，但不能进入行坐标和列坐标的位数之和大于k的格子。*例如当k为18时，机器人可以进入方格(35,37)，因为3+5+3+7=18。*但是不能进入格子(35,38)，因为3+5+3+8=19。机器人可以到达多少个格子？*@parammatrix矩阵*@paramthreshold临界点（最大活动范围）*/publicmovingCount(matrix:Array>,threshold=0):number{if(threshold<0||matrix.length<=0){return0;}//获取网格的总行数和列数constrows=matrix.length;constcols=matrix[0].length;//创建标记数组，标识网格是否被访问constisVisited:Array>=newArray(rows);for(leti=0;i();consttotalCount=backtracking.movi??ngCount(pathArr,4);constpath=backtracking.path;console.log("机器人总共能走的格子总数为：",totalCount,",movement轨迹为：",path.substr(0,path.length-3));执行结果如下：
