题目

题解

1. DFS

利用递归实现DFS搜索，注意要使用一个额外的矩阵保存已经访问过的位置，防止重复访问。当越界或者不满足数位条件或者已经访问过的时候剪枝。
另外只需要向右下搜索就可以，因为数组是从左上开始的。

  • 时间复杂度$O(m*n)$
  • 空间复杂度$O(m*n)$
class Solution {//两个方法。1.DFS
public:
    int get(int n){//计算位数和
        int sum = 0;
        while(n>0){
            sum += n%10;
            n /= 10;
        }
        return sum;
    }
    int dfs(vector<vector<bool>>& vis, int i, int j, int m, int n, int k){
        if(i<0 || j<0 || i>=m || j>=n || get(i)+get(j)>k || vis[i][j]==true) return 0;
        vis[i][j] = true;
        int res = 1 + dfs(vis, i+1, j, m, n, k) + 
                  dfs(vis, i, j+1, m, n, k);//只用搜索右下就可以，因为是从左上开始的
        return res;
    }
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> vis(m,vector<bool>(n));//存访问过的数组，防止重复访问
        return dfs(vis, 0, 0, m, n, k);
    }
};

2. BFS

用队列实现BFS
注意这个的顺序，是先判断下一个位置是否符合条件再加入队列，，即加入队列的位置全部是作为寻找下一个节点的种子。

  • 时间复杂度$O(m*n)$
  • 空间复杂度$O(m*n)$
class Solution {//两个方法。2.BFS
public:
    int get(int n){//计算位数和
        int sum = 0;
        while(n>0){
            sum += n%10;
            n /= 10;
        }
        return sum;
    }
    int movingCount(int m, int n, int k) {
        int res = 1;
        vector<vector<bool>> vis(m, vector<bool>(n,false));//存是否访问过
        int dx[2] = {0,1};
        int dy[2] = {1,0};//指向右下搜索就可以
        queue<pair<int,int>> q;//队列完成BFS
        q.push(make_pair(0,0));//先存第一个数
        vis[0][0] = true;
        while(!q.empty()){
            auto [x,y] = q.front();//这个写法看题解的，觉得很牛逼啊
            q.pop();//弹出队首
            for(int i=0; i<2; ++i){
                int nx = x + dx[i];
                int ny = y + dy[i];//下个位置的坐标
                //判断是否符合条件，不符合跳过本次循环
                if(nx<0 || ny<0 || nx>=m || ny>=n || vis[nx][ny]==true || get(nx)+get(ny)>k) continue;
                //符合就加入队列，vis置为true，并res++计一个位置
                q.push(make_pair(nx,ny));
                vis[nx][ny] = true;
                res++;
            }
        }
        return res;
    }
};