当前位置 博文首页 > 中流击水,浪遏飞舟:dfs&&bfs&&剑指 Offer 13.
class Solution {
public:
//需要做的操作:取数位和,判断,叠加返回值
//递归解法
int row,col,maxnum=1;
int digital(int i){ //取数位和函数
int count=0;
while(i){
count+=(i%10);
i/=10;
}
return count;
}
int dfs(int i,int j,int sum,int k,vector<vector<bool>>& f){
if(sum>k || f[i][j]){
return 0;
}
f[i][j]=true; //防止遍历回去
int dx[]={0,1}; //只需要遍历下方和右方
int dy[]={1,0};
for(int t=0;t<2;t++){
int x=i+dx[t];
int y=j+dy[t]; //这一步原始写成dx[t]了,查了好久错误。。。
if(x<0 || x>=row || y<0 || y>=col){
continue;
}
sum=digital(x)+digital(y);
maxnum+=dfs(x,y,sum,k,f);
}
//f[i][j]=true; //不需要恢复现场,因为一个单元格只访问一次
return 1;
}
int movingCount(int m, int n, int k) {
vector<vector<bool>> f(m,vector<bool>(n,false)); //标志数组
row=m;
col=n;
dfs(0,0,0,k,f);
return maxnum;
}
};
参考了大神回答:
剑指 Offer 13. 机器人的运动范围( 回溯算法,DFS / BFS ,清晰图解)
class Solution {
public:
//参考K神的数位和增量公式和可达解
int dfs(int i,int j,int x,int y,int m,int n,int k,vector<vector<bool>>& f){
if(i>=m || j>=n || x+y>k || f[i][j]){ //只需要遍历下方和右方即可
return 0;
}
f[i][j]=true; //防止遍历回去
return 1+dfs(i+1,j,((i+1)%10!=0)?x+1:x-8,y,m,n,k,f)+dfs(i,j+1,x,((j+1)%10!=0)?y+1:y-8,m,n,k,f); //i+1右边||j+1下边
}
int movingCount(int m, int n, int k) {
vector<vector<bool>> f(m,vector<bool>(n,false)); //标志数组
return dfs(0,0,0,0,m,n,k,f);
}
};