public class Solution { int rows,cols; int[][] vis; int cnt = 0; int dis(int x, int y){ int sum=0; int tmp=x; while(tmp>0){ sum+=tmp%10; tmp/=10; } tmp=y; while(tmp>0){ sum+=tmp%10; tmp/=10; } return sum; } public int movingCount(int threshold, int rows, int cols) { this.vis = new int[rows][cols]; this.rows = rows; this.cols = cols; if(threshold < 0) return 0; else if(threshold == 0) return 1; count(threshold,0,0); return cnt; } void count(int hold, int x, int y){ if(x>=rows || y>=cols || vis[x][y] == 1) return; if(dis(x,y) > hold) return; cnt++; vis[x][y] = 1; count(hold,x+1,y); // turn down count(hold,x,y+1); // turn right } }
使用BFS或者DFS都可以,这里我使用了DFS。
在DFS内先进行边界判断:
如果已经访问过或者越界了,那么直接返回。
如果上面的条件可以通过,说明可以到达该点,计数器加一。
然后继续向右向下递归。