算法

(DFS)

C++ 代码

class Solution {
public:
    bool vis[50][50];
    int sum(int i){
        int res=0;
        while(i>0){
            res+=i%10;
            i=i/10;
        }
        return res;
    }
    void dfs(int threshold,int rows, int cols,int i,int j,int &num){
        if(sum(i)+sum(j)>threshold)return;
        vis[i][j]=true;
        num++;
        if(i>0&&vis[i-1][j]==false)dfs(threshold,rows,cols,i-1,j,num);
        if(i<rows-1&&vis[i+1][j]==false)dfs(threshold,rows,cols,i+1,j,num);
        if(j>0&&vis[i][j-1]==false)dfs(threshold,rows,cols,i,j-1,num);
        if(j<cols-1&&vis[i][j+1]==false)dfs(threshold,rows,cols,i,j+1,num);
    }
    int movingCount(int threshold, int rows, int cols)
    {
        int num=0;
        if(rows==0||cols==0)return 0;
        dfs(threshold,rows,cols,0,0,num);
        return num;

    }
};