机器人的运动范围

地上有一个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

提示：

• 1 <= n,m <= 100
• 0 <= k <= 20

思路一：

dfs,深度优先遍历每一个格子，如果当前格子满足条件，则计数加1。运动的过程中，可以只考虑向下和向右，因为向上的格子，要么被向下方向走过，要么会被向右方向走过。向右同理。所以只需要考虑向下和向右。

代码

class Solution {
private:
    int ans = 0;
    vector<vector<int>> visited;
public:
    int getDigits(int x) {
        int a = 0;
        while (x > 0) {
            a += x%10;
            x /= 10;
        }
        return a;
    }
    void dfs(int m,int n,int i,int j,int k) {
        if (i>=0 && i < m && j >= 0 && j < n && getDigits(i)+getDigits(j)<=k && visited[i][j] == false) {
            //当前位置满足条件，计数加一，并且记录，防止重复计算。
            ans++;
            visited[i][j] = true;
            vector<vector<int>> directions = {{0,1},{1,0}};
            for(const auto& dir: directions) {
                int newI = i+dir[0];
                int newJ = j+dir[1];
                dfs(m, n, newI, newJ, k);
            }
        }
    }
    int movingCount(int m, int n, int k) {
        ans = 0;
        visited.resize(m, vector<int>(n));
        dfs(m, n, 0, 0,k);
        return ans;
    }
};

思路2:

bfs,广度遍历每一个格子，统计满足条件的格子个数。因为只考虑向左和向下，所以其实整个遍历路径就是一棵二叉树。可以使用二叉树的层序遍历方法。

class Solution {
public:
    int getDigitsSum(int x) {
        int ans = 0;
        while(x > 0) {
            ans += x%10;
            x /= 10;
        }
        return ans;
    }
    int movingCount(int m, int n, int k) {
        if(k < 0 || m <= 0 || n <= 0) {
            return 0;
        }
        queue<pair<int,int>> que;
        que.push({0,0});
        int ans = 1;
        vector<pair<int,int>> directions{{0,1},{1,0}};
        vector<vector<bool>> visited(m,vector<bool>(n));
        visited[0][0] = true;
        while(!que.empty()) {
            auto p = que.front();
            que.pop();
            for(const auto& direction: directions) {
                int newRow = direction.first + p.first;
                int newCol = direction.second + p.second;
                if(newRow >= 0&& newRow < m&& newCol >= 0&& newCol < n && getDigitsSum(newRow)+getDigitsSum(newCol) <= k && !visited[newRow][newCol]) {
                    ans++;
                    que.push({newRow,newCol});
                    visited[newRow][newCol] = true;
                }
            }
        }
        return ans;
    }
};

思路3:

动态规划。记dp[i][j]，表示机器人能否进入位置(i,j),如果i和j的数位之和小于等于k，而机器人从(i-1,j)或者(i,j-1)位置移动而来，如果i == 0,j==0,则dp[i][j] = true,如果i!=0,j==0则dp[i][j] = dp[i-1][j]，如果i==0,j!=0则dp[i][j] = dp[i][j-1],如果i!=0,j!=0，则dp[i][j]=dp[i-1][j] | dp[i][j-1]。如果dp[i][j]==true，则格子数加1

代码：

class Solution {
public:
    int getDigitsSum(int x) {
        int ans = 0;
        while(x > 0) {
            ans += x%10;
            x /= 10;
        }
        return ans;
    }
    int movingCount(int m, int n, int k) {
        if(k < 0 || m <= 0 || n <= 0) {
            return 0;
        }
        vector<vector<bool>> memery(m,vector<bool>(n));
        int ans = 0;
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                if(getDigitsSum(i)+getDigitsSum(j) <= k) {
                    if(i == 0 && j == 0) {
                        memery[i][j] = true;
                    }
                    else if(i > 0 && j == 0) {
                        memery[i][j] = memery[i-1][j];
                    }
                    else if(j > 0 && i == 0) {
                        memery[i][j] = memery[i][j-1];
                    }
                    else {
                        memery[i][j] = memery[i-1][j] | memery[i][j-1];
                    }
                    ans += memery[i][j];
                }
            }
        } 
        return ans;
    }
};