剑指 Offer 13. 机器人的运动范围

剑指 Offer 13. 机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

示例 2：

输入：m = 3, n = 1, k = 0
输出：1

这个题目描述的不是很清楚，最后看了评论才明白这个题目什么意思，DFS

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vectorint>> v(m,vector<int>(n,0));
        int sum=0;
        dfsFind(0, 0, m, n, k,sum,v);
        return sum;
    }
    int Suan(int i,int k) {
        int ii = i;
        int sumi = 0;
        while (ii != 0) {
            sumi += ii % 10;
            ii = ii / 10;
        }
        return sumi;
    }
    void dfsFind(int i, int j, int m, int n, int k, int &sum, vectorint>> &v) {
        if (i >= m || j >= n|| v[i][j] == 1)
            return;
        v[i][j] = 1;
        int ii = Suan(i, k);
        int jj = Suan(j, k);
        if (ii > k || jj > k||ii+jj>k)
            return;
        sum++;
        ii = i + 1;
        jj = j + 1;
        dfsFind(ii, j, m, n, k, sum,v);
        dfsFind(i, jj, m, n, k, sum,v);
    }
};