虽然机器人可以上下左右移动,但是从(0,0)出发向下、向右遍历已经可以遍历所有满足要求的节点
因此只需向下向右进行递归,类似二叉树,因为会出现重复,用二维数组进行标记
public class Solution { public int movingCount(int threshold, int rows, int cols) { boolean flag[][]=new boolean[rows][cols]; return dfs(threshold,rows,cols,0,0,flag); } public int dfs(int target,int x,int y,int curX,int curY,boolean flag[][]){ int temp=0;//坐标位数和 for(int i=curX;i>0;i/=10){ temp+=(i%10); } for(int j=curY;j>0;j/=10){ temp+=(j%10); }//终止条件 if(curX<0||curX>=x||curY<0||curY>=y||temp>target||flag[curX][curY]){ return 0; } flag[curX][curY]=true;//标记 return (dfs(target,x,y,curX+1,curY,flag)+dfs(target,x,y,curX,curY+1,flag))+1; //递归求解从每个坐标出发可到达的格子数 } }