请注意:本文只包含dfs的内容 /如有错误或者意见,欢迎留言
模拟机器人走路,在符合条件的情况下,上下左右走,走到符合条件的格子,标记/累加。走完即可。
1.越界情况,x,y的值得在符合二维数组范围的情况下进行
2.走过的点,不需要累加/标记
3.x,y坐标相加是否大于k的时
最近看到一条定理:一直在变化的数,就可以用于dfs的参数。
这里我选择了,x,y坐标的值作为dfs的参数
1 2 3 4 5
| 是否可以直接遍历出x,y相加的值, 记录于二维数组中, 从而直接得出答案(没试过); 提示:不能直接判断哦,看清楚上下左右;
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| class Solution { public: int k,row,col; //row代表行,col代表列 int n; //用于答案计数 int a[100][100]; int movingCount(int threshold, int rows, int cols) { memset(a,0,sizeof(a)); k=threshold,row=rows,col=cols; dfs(0,0); return n; } int he(int x,int y) //用于计算x,y的和(题意中的和) { int res=0; while(x) { res+=x%10; x/=10; } while(y) { res+=y%10; y/=10; } return res; } void dfs(int x,int y) { if(x<0||y<0||x>=row||y>=col) return; //边界判定 if(a[x][y]==1) return; //是否已经走过这个点 if(he(x,y)>k) return; //如果x+y大于k的话(不符合条件) //剩下的符合条件的情况 的操作 a[x][y]=1; n++; dfs(x-1,y); //上 dfs(x+1,y); //下 dfs(x,y-1); //左 dfs(x,y+1); //右
return; } };
|