剑指 Offer 13 机器人的运动范围
概述
https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
深度优先搜索 / 递归法
每个格子最多访问一次,因此时间复杂度 O(mn)
。
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>> flags(m, vector<bool>(n, false));
return dfs(flags, m, n, k, 0, 0);
}
int dfs(vector<vector<bool>>& flags, int m, int n, int k, int i, int j) {
if (i < 0 || j < 0 || i >= m || j >= n || flags[i][j] || !okay(i, j, k)) return 0;
flags[i][j] = true;
int count = 1 + dfs(flags, m, n, k, i + 1, j) + dfs(flags, m, n, k, i, j + 1)
+ dfs(flags, m, n, k, i - 1, j) + dfs(flags, m, n, k, i, j - 1);
return count;
}
bool okay(int i, int j, int k) {
return (i / 10 + j / 10 + i % 10 + j % 10) <= k;
}
};
迭代法
考虑到开始位置为左上角,且 bot 必须从已可到达的位置前往下一个位置,即不能跳跃, 因此判断一个格子可不可达只需要判断其上边和左边的是否可达,所以我们可以按照从上到下,从左到右的顺序遍历整个棋盘即可。
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>> flags(m, vector<bool>(n, false));
int count = 0;
for (int i=0; i < m; i++) {
for (int j=0; j < n; j++) {
if (!okay(i, j, k)) continue;
if (i == 0 && j == 0) flags[i][j] = true;
if (i > 0 && flags[i-1][j]) flags[i][j] = true;
if (j > 0 && flags[i][j-1]) flags[i][j] = true;
if (flags[i][j] == true) {
count += 1;
}
}
}
return count;
}
bool okay(int i, int j, int k) {
return (i / 10 + j / 10 + i % 10 + j % 10) <= k;
}
};
迭代法(早停优化)
行首不行的话,该行其余元素也必然不行,这又将导致剩余行也必然不行。
但要注意,对于非行首元素,不能因为其不行就断言其之后的也不行,因为它之后的元素的数位和未必比它大,例如 19 和 23。
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>> flags(m, vector<bool>(n, false));
int count = 0;
for (int i=0; i < m; i++) {
if (!okay(i, 0, k)) break; # 这里!
for (int j=0; j < n; j++) {
if (!okay(i, j, k)) continue;
if (i == 0 && j == 0) flags[i][j] = true;
if (i > 0 && flags[i-1][j]) flags[i][j] = true;
if (j > 0 && flags[i][j-1]) flags[i][j] = true;
if (flags[i][j] == true) {
count += 1;
}
}
}
return count;
}
bool okay(int i, int j, int k) {
return (i / 10 + j / 10 + i % 10 + j % 10) <= k;
}
};
广度优先搜索
维护一个队列,其中记录当前可以探索的点,探索该点后将新的可探索点加入队列,同时踢出该点。
Links: sword-offer-13