放荡的人生|经典算法——机器人的路径例如

机器人的运动范围【放荡的人生|经典算法——机器人的路径】地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。
例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7=18 。但是，它不能进入方格（35,38），因为3+5+3+8=19 。请问该机器人能够达到多少个格子？
思路：从起点坐标(0,0)开始移动，每成功走过一个格子，就把该位置值设为1 ，然后从当前位置开始上、下、左、右进行移动，返回四个方向移动值之和并加1 。
publicintmovingCount(intthreshold,introws,intcols){//初始化一个m行n列的标志数组intflag[][]=newint[rows][cols];//以(0,0)位置开始移动returnhelper(0,0,rows,cols,flag,threshold);}publicinthelper(inti,intj,introws,intcols,int[][]flag,intthreshold){//如果当前位置不在矩阵内，即i<0或j<0或i>=rows或j>=cols ，即当前位置不可到达。 //若当前位置坐标不满足条件即numSum(i)和大于限定值，即当前位置不可到达。 //若当前位置已经被访问过，即flag标志为1 ，则该位置不可再次到达。 if(i<0||j<0||i>=rows||j>=cols||numSum(i)+numSum(j)>threshold||flag[i][j]==1){return0;}flag[i][j]=1;returnhelper(i-1,j,rows,cols,flag,threshold)+helper(i+1,j,rows,cols,flag,threshold)+helper(i,j-1,rows,cols,flag,threshold)+helper(i,j+1,rows,cols,flag,threshold)+1;}publicintnumSum(inti){//计算单个坐标值的累加和intsum=0;do{sum+=i%10;}while((i=i/10)>0);returnsum;}矩阵中的路径请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如abcesfcsadee矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
//给定的输入矩阵matrix是一个一维数组publicbooleanhasPath(char[]matrix,introws,intcols,char[]str){//标志位，初始化为falseboolean[]flag=newboolean[matrix.length];for(inti=0;i=rows||j>=cols||matrix[index]!=str[k]||flag[index]==true){returnfalse;}//若k等于str.length-1 ，说明已经匹配成功，返回trueif(k==str.length-1){returntrue;}//给当前位置置为true ，说明已经走到了flag[index]=true;//然后上、下、左、右寻找下一个位置if(judge(matrix,i-1,j,rows,cols,flag,str,k+1)||judge(matrix,i+1,j,rows,cols,flag,str,k+1)||judge(matrix,i,j-1,rows,cols,flag,str,k+1)||judge(matrix,i,j+1,rows,cols,flag,str,k+1)){returntrue;}//走到这，说明这一条路不通，还原，再试其他的路径flag[index]=false;returnfalse;}