机器人运动范围
机器人的运动范围
http://www.nowcoder.com/questionTerminal/6e5207314b5241fb83f2329e89fdecc8
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内先进行边界判断：
如果已经访问过或者越界了，那么直接返回。
如果上面的条件可以通过，说明可以到达该点，计数器加一。
然后继续向右向下递归。
