第五十一题 回溯第二题
考虑由两个方向是否有路径
之前处理第一行的时候，因为没有从上面来的路径，所以一旦不符合threshold，就直接break了，但是后面行是有来自于上面的路径的时候的，所以必须要考虑进去
如图：对于第六行 假设要求各位和不能超过15，此时6+9=15，符合，6+1+0=7 后面都符合。。。。。
然后看到第七行，7+9=16 不符合了，但是7+1+0=8符合要求，按照要求看是否有路径，左边来不了，但是可以从上面下来，所以往后都是符合的

class Solution {
public:
    int movingCount(int threshold, int rows, int cols) {
        int ans=0;
        // 记录某个位置是否可以访问到
        int tempvec[rows][cols];
        for(int i=0;i<rows;i++)
            for(int j=0;j<cols;j++)
                tempvec[i][j]=0;
        
        // 初始化第一行
        // 第一行上面没有东西了，所以只看从左向右的路径
        // 一旦超了，后面就都访问不到了
        // 实例3中，访问到了0,28这一点，后面都不能访问了，虽然说可以0,30符合要求，但是因为 0,29点到不了，所以后面都不能访问
        tempvec[0][0]=1;
        for(int i=0;i<cols;i++)
        {
            // 判断ij可不可以，可以的话ans++
            int temp=0;
            int tempi=i;
            while(tempi!=0){
                temp+=tempi%10;
                tempi=tempi/10;
            }
            if(temp<=threshold){
                ans++;
                tempvec[0][i]=1;
            }
            else
                break;
        }
        
        // 然后开始向后面的所有行开始遍历
        for (int i=1;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                // 判断ij可不可以，可以的话ans++
                int temp=0;
                int tempi=i;
                int tempj=j;
                // ij按位求和
                while(tempi!=0)
                {
                    temp+=tempi%10;
                    tempi=tempi/10;
                }
                while(tempj!=0){
                    temp+=tempj%10;
                    tempj=tempj/10;
                }
                // 点可以访问的两个要求：1.点的坐标和符合要求；2.点能有路径到
                // 1就不细说了
                // 主要看2：之前说了，实例三中后面是不能访问的，但是考虑到后面的行，就要考虑是不是可以从上面下来！
                // 不方便说，看后面的图
                
                // 如果说 符合要求 并且 (左边有路 或者 上面有路)那么结果正确
                if(temp<=threshold && ( tempvec[i-1][j]==1 || tempvec[i][j-1]==1) )
                {
                    ans++;
                    tempvec[i][j]=1;
                }
            }
        }
        
        
        // 可以访问到的点的二维数组输出
        /*
        for (int i=1;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                cout<<tempvec[i][j]<<" ";
            }
            cout<<endl;
        }*/
        
        return ans;
    }
};