public class Solution { public int movingCount(int threshold, int rows, int cols) { //边界条件 if(threshold<0||rows<=0||cols<=0){ return 0; } //标记数组,判断节点是否被访问,初始值都为false boolean[][] isVisited=new boolean[rows][cols]; //dfs算法,格子数等于后面计算的加上(0,0) return depthFirstSearch(threshold,rows,cols,0,0,isVisited)+1; } //i与j为当前搜索节点在矩阵中的坐标 private int depthFirstSearch(int threshold,int rows,int cols,int i,int j,boolean[][] isVisited){ //边界条件 if(i>=rows||j>=cols||i<0||j<0){ return 0; } //设置当前节点被访问 isVisited[i][j]=true; int number=0; //定义方向 int[] dx={1,-1,0,0}; int[] dy={0,0,1,-1}; //访问(i,j)的下一个节点(X,Y) for(int k=0;k<4;k++){ //(X,Y)为(i,j)的下一个移动的坐标 int X=i+dx[k]; int Y=j+dy[k]; //(X,Y)节点满足1、阈值大小2、节点坐标未出界3、当前节点未被访问,再去访问下一个节点 if(X>=0&&Y>=0&&(sumOfValue(X)+sumOfValue(Y))<=threshold&&X<rows&&Y<cols&&isVisited[X][Y]==false){ //递归,格子数目等于后面递归的格子数+1; number+=depthFirstSearch(threshold,rows,cols,X,Y,isVisited)+1; } } return number; } //判断阈值大小哦 private int sumOfValue(int number){ int sum=0; while(number!=0){ sum+=number%10; number=number/10; } return sum; } }