题目
面试题13. 机器人的运动范围 是剑指offer的一道题
灵感来源:
200. 岛屿数量
思路
考的图论
floodfill算法
惊喜
照猫画虎居然直接过了!
代码
class Solution {
public:
int sum(int x){//计算数位和
int count = 0;
while(x){
count += x%10;
x /= 10;
}
return count;
}
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//左上右下
int res = 0;
int m , n , k;
vector<vector<bool>>st;
int movingCount(int _m, int _n, int _k) {
//m行n列
//不能进入行坐标和列坐标的"数位"之和大于k的格子
// i + j > k
m = _m, n = _n, k = _k;
vector<vector<bool>>_st(m,vector<bool>(n));//初始化
st = _st;
return dfs(0,0);
}
int dfs(int x, int y){
st[x][y]=true;
res++;
for(int i = 0 ;i < 4 ; i++){
int a = x+dx[i] , b = y + dy[i];
if(a >= 0 && a < m && b >= 0 && b < n && !st[a][b] && sum(a)+sum(b)<=k){
dfs(a,b);//那么我们就渲染一下
}
}
return res;
}
};