记忆点
- 递归
- 从
开始
思路
用递归。
目标是从开始，找到所有的可以访问的点，所以理论上矩阵上的每个点最多访问一次。
实现
class Solution {
public:
int getSum (int x, int y) {
int s = 0;
while (x) {
s += x % 10;
x /= 10;
}
while (y) {
s += y % 10;
y /= 10;
}
return s;
}
int step(int x, int y, int threshold, vector<vector<bool>>& visited) {
if (x < 0 || x >= visited.size() || y < 0 || y >= visited[x].size()) return 0;
if (visited[x][y] || getSum(x, y) > threshold) return 0;
int cnt = 1;
visited[x][y] = true;
cnt += step(x+1, y, threshold, visited);
cnt += step(x-1, y, threshold, visited);
cnt += step(x, y+1, threshold, visited);
cnt += step(x, y-1, threshold, visited);
return cnt;
}
int movingCount(int threshold, int rows, int cols) {
if (threshold < 0 || rows <= 0 || cols <= 0) return 0;
int cnt = 0;
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
cnt += step(0, 0, threshold, visited);
return cnt;
}
};
