题目描述
blablabla
样例
blablabla
看上去代码很多,其实这个不难
这个题,使用dfs主要注意是两个:
1.不重复搜索(不多加,所以要使用st数组)
2.控制遍历的方向(方向数组)
可能遇到的问题:dfs直接使用,然后四个方向遍历,因为不会有回退操作,所以st不需要再赋值false,还有大家可能会多搜,什么意思。
就是比如输入3 13 14,可能会出现输出25。为什么,刚开始我一直想不通,右边的数不应该比左边的数大吗,res应该不会加才对。就是如果k = 4 ,矩阵中x = 1,y = 4的时候,他的右边不应该都是不满足的吗。
平常是这样的,但是我们求的是各位置之和 如k = 4,但搜索到矩阵中 x = 1 ,y = 10(如果有这个测试用例)sum = 1 + 1 + 0 = 2 < 4 就是这个点可以去,但是去的了吗? 机器人在x = 1 ,y = 4 的时候就不能往右走了。
问题出现在哪:dfs遍历四个方向的,有个方向出现不能遍历的时候,我们应该提前舍弃而不是让它继续走,所以if判断中的sum(a,b) <= k 必不可少
总结下:存在方向的遍历,需要先定义st数组,防止重复。定义方向数组,确定方向。这道题是限定了,一个方向走不了,我们要提前舍弃,而不是继续走。
附图:输入为 3,13,14 下输出为25个和10个情况
为10个情况
我习惯使用n,m作为全局变量,所以多定义了,大家将就看看就行,前面有个老哥写的比较简洁,可以参考他的代码。
代码
class Solution {
int res = 0;
int[] dx = {-1,0,1,0},dy = {0,1,0,-1};
boolean[][]st ;
int n,m;
public int movingCount(int threshold, int rows, int cols)
{
if(rows == 0||cols == 0)return 0;
n = rows;m = cols;
st = new boolean[n + 1][m + 1];
dfs(0,0,threshold);
return res;
}
//从四个方向去遍历
private void dfs(int x, int y,int k){
if(st[x][y])return;
st[x][y] = true;
if(sum(x,y) <= k){
res++;
}
for(int i = 0; i < 4 ;i ++){
int a = x + dx[i],b = y + dy[i];
//if中sum(a,b) <= k必不可少
if(a >= 0 && a < n && b >= 0 && b < m && !st[a][b] && sum(a,b) <= k){
dfs(a,b,k);
}
}
}
//求和,不多说
private int sum(int x, int y){
int t = 0;
while(x>0){
t+=x%10;
x/=10;
}
while(y>0){
t+=y%10;
y/=10;
}
return t;
}
}