【剑指offer66 机器人的运动范围】

class Solution {
    int get(int x) {
        //返回各位数值之和
        int res=0;
        for (; x; x /= 10){
            res += x % 10;
        }
        return res;
    }
    
public:  
    int movingCount(int k, int m, int n)
    {
        if(k<=0)return 0;
        if (!k) return 1; //k=0的情况
        int vis[m][n] ; //记录是否可访问到
        memset(vis,0,sizeof(vis));
        int ans = 1;
        vis[0][0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                //判断起点  以及  条件
                if ((i == 0 && j == 0) || get(i) + get(j) > k) continue;
                //满足条件后   边界判断   判断机器人是否能够移动到此点
                //只可能是从左边 或者上面过来的  所以只判断这两个方向可不可达就行
                //if (i - 1 >= 0) vis[i][j] |= vis[i - 1][j]; //或 等于  做或运算
                //if (j - 1 >= 0) vis[i][j] |= vis[i][j - 1];
                
                if (i - 1 >= 0 && vis[i-1][j])vis[i][j]=1; 
                if (j - 1 >= 0 && vis[i][j-1])vis[i][j]=1;
                ans += vis[i][j]; //如果不可达 自然为0
            }
        }
        return ans;
    }
};