题解 | #机器人的运动范围#

#include <vector>
class Solution 
{
public:
    int sum(int n)
    {
        int sum = 0;
        while(n)
        {
            sum += n%10;
            n /= 10;
        }
        return sum;
    }

    bool maxCount(int& threshold, int& rows, int& cols,vector<vector<bool>> &dp,int i,int j,int& max)
    {
        if(i < 0 || i >= rows || j < 0 || j >= cols || dp[i][j] || threshold < sum(i) + sum(j))
            return false;
        max++;
        dp[i][j] = true;

        int w[2][4] = {{0,1,0,-1},{1,0,-1,0}};

        int x,y;
        for(int k = 0;k < 4;k++)
        {
            x = i + w[0][k],y = j + w[1][k];
            if(maxCount(threshold,rows,cols,dp,x,y,max))
                return true;
        }

        return false;
    }

    int movingCount(int threshold, int rows, int cols) 
    {
        vector<vector<bool>> dp(rows,vector<bool>(cols,false));//记录格子是否走过
        int max = 0;

       maxCount(threshold,rows,cols,dp,0,0,max);
        return max;
    }
};