算法：DFS+剪枝

经典的DFS算法，走迷宫的变种，注意递归边界和矩阵边界

时间复杂度

$O(NM)$

代码

class Solution {
public:
    int ans = 0;
    vector<vector<bool>> vis;
    int get(int i, int j){
        int res = 0;
        while(i > 0){
            res += i % 10;
            i /= 10;
        }  
        while(j > 0){
            res += j % 10;
            j /= 10;
        }

        return res;
    }
    int movingCount(int m, int n, int k) {
        vis.resize(m, vector<bool>(n));
        dfs(0, 0, m, n, k);
        return ans;
    }
    void dfs(int i, int j, int m, int n, int k){
        vis[i][j] = true;
        // cout<< i << ' '<<j<<' '<<get(i,j)<<endl; 
        if(get(i,j) <= k) ans ++;
        else return; // 递归边界
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        for(int t = 0; t < 4; t ++){
            int x = i + dx[t], y = j + dy[t];
            // cout<<x<<' '<<y<<endl;
            if(x < m && x >= 0 && y < n && y >= 0 && !vis[x][y]) dfs(x, y, m, n, k); // 矩阵边界
        }
    }
};