一开始的误解:
以为满足数位之和<=k的地方都能到,实际上有可能是到不了的,因为不是x+y而是x的每一位和y的每一位相加!!!
思路(就是二维数组中地图中相邻1的个数,套模板即可,模板记不清了)
1:BFS
int xy[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
bool flag[m][n];
queue<pair<int, int>> q;
q.push(make_pair(0, 0));
flag[0][0] = true;
while (!q.empty()) {
pair<int, int> top = q.front();
//对队头元素操作
q.pop();
for (int i = 0; i < 4; ++i) {
int xx = top.first + xy[i][0];
int yy = top.second + xy[i][1];
if (xx < 0 || xx > m - 1 || yy < 0 || yy >n - 1) continue;
if (map[xx][yy]满足条件 && !flag[xx][yy]) {
q.push(make_pair(xx, yy));
flag[xx][yy] = true;
}
}
}
2:DFS
void dfs(int x, int y) {
if (map[x][y]满足条件 && !flag[x][y]) { //先对当前坐标进行处理!!!
flag[xx][yy] = true;
}
for (int i = 0; i < 4; ++i) {
int xx = x + xy[i][0];
int yy = y + xy[i][1];
if (xx < 0 || xx > m - 1 || yy < 0 || yy >n - 1) continue;
if (map[xx][yy]满足条件 && !flag[xx][yy]) {
dfs(xx, yy);
flag[xx][yy] = true;
}
}
}
题目代码粘贴(BFS)
class Solution {
public:
int xy[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int getsum(int m){
int sum=0;
while(m){
sum += (m%10);
m /= 10;
}
return sum;
}
int movingCount(int m, int n, int k) {
vector<vector<bool>> v(m, vector<bool>(n)); //能移位标记为true
vector<vector<bool>> flag(m, vector<bool>(n)); //搜索过标记为true
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int sum1 = getsum(i), sum2 = getsum(j);
if (sum1 + sum2 <= k) {
v[i][j] = true;
}
}
}
int ans = 0;
queue<pair<int, int>> q;
q.push(make_pair(0, 0));
flag[0][0] = true;
while (!q.empty()) {
pair<int, int> top = q.front();
ans++;
q.pop();
for (int i = 0; i < 4; ++i) {
int xx = top.first + xy[i][0];
int yy = top.second + xy[i][1];
if (xx < 0 || xx > m - 1 || yy < 0 || yy >n - 1) continue;
if (v[xx][yy] && !flag[xx][yy]) {
q.push(make_pair(xx, yy));
}
flag[xx][yy] = true;
}
}
return ans;
}
};
题目代码粘贴(DFS)
class Solution {
public:
int xy[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int v[105][105];
int flag[105][105];
int getsum(int m){
int sum=0;
while(m){
sum += (m%10);
m /= 10;
}
return sum;
}
void dfs(int x, int y, int &ans, int &m, int &n) {
if (v[x][y] && !flag[x][y]) {
ans++;
flag[x][y] = true;
}
for (int i = 0; i < 4; ++i) {
int xx = x + xy[i][0];
int yy = y + xy[i][1];
if (xx < 0 || xx > m - 1 || yy < 0 || yy > n - 1) continue;
if (v[xx][yy] && !flag[xx][yy]) {
ans++;
flag[xx][yy] = true;
dfs(xx, yy, ans, m, n);
}
}
}
int movingCount(int m, int n, int k) {
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int sum1 = getsum(i), sum2 = getsum(j);
if (sum1 + sum2 <= k) {
v[i][j] = true;
}
}
}
int ans = 0;
dfs(0, 0, ans, m, n);
return ans;
}
};