一、题目描述

JZ66机器人的运动范围
题目大意：上有一个rows行和cols列的方格。坐标从 [0,0] 到 [rows-1,cols-1]。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于threshold的格子。 例如，当threshold为18时，机器人能够进入方格[35,37]，因为3+5+3+7 = 18。但是，它不能进入方格[35,38]，因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

二、算法1（BFS）

解题思路

  1. 审题后我们发现，本题其实就是一个带附加条件的搜索问题，因此用DFS或BFS都可以解决，这里用BFS解决
  2. 首先，机器人每次只能向上、下、左、右四个方向移动，并且只有当目标点横纵坐标的数位之和不大于threshold才能移动
  3. 算法实现：用一个二维布尔数组标记坐标的访问状态，再创建一个队列存放坐标，最初先将起点(0, 0)如队，每次出队一个元素就记录一次答案，然后根据出队坐标尝试向四周扩散，若有可行点，就将其标记后入队，直到队列为空算法结束；对于求数位和，每次模10可以得到最低位，然后再除以10，直到参数为0为止结束

图片说明

代码实现（C++11）

class Solution {
public:
    const int dxy[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    int movingCount(int threshold, int rows, int cols) {
        auto get = [](int x)->int {    // 求x的数位之和
            int res = 0;
            while(x){
                res += x % 10;
                x /= 10;
            }
            return res;
        };
        vector<vector<bool>> st(rows, vector<bool>(cols, 0));     // 二维布尔数组标记坐标
        int ans = 0;
        queue<pair<int, int>> q;
        q.push({0, 0});    // 初始点入队
        st[0][0] = true;
        while(q.size()){
            auto p = q.front(); q.pop();
            int x = p.first, y = p.second;
            ++ans;
            for(int i = 0; i < 4; i++){    // 尝试向四周移动
                int dx = x + dxy[i][0], dy = y + dxy[i][1];
                if(dx >= 0 && dx < rows && dy >= 0 && dy < cols && !st[dx][dy] && get(dx) + get(dy) <= threshold){
                    st[dx][dy] = true;
                    q.push({dx, dy});
                }
            }
        }

        return ans;
    }
};

时间复杂度：O(rows * cols)，最多每个元素都入队一次出队一次
空间复杂度：O(rows * cols)，队列和布尔数组占用的空间

三、算法2（动态规划）

解题思路

  1. 由此题我们可以联想到经典数字三角形模型，定义状态数组f(i, j)表示(i, j)这点是否能被访问到，对于每一点的状态f(i, j)，可以从(i - 1, j)和(i, j - 1)转移而来，f(i, j) = true表示(i, j)这点可以到达，反之不能
  2. 在进行状态转移时一定要注意边界问题(i - 1, j)或(i, j - 1)不一定都存在
  3. 故状态转移方程为：
    图片说明

代码实现（C++11）

class Solution {
public:
    int movingCount(int threshold, int rows, int cols) {
        auto get = [](int x)->int {    // 求x的数位之和
            int res = 0;
            while(x){
                res += x % 10;
                x /= 10;
            }
            return res;
        };
        int ans = 1;    // 起点算一种
        vector<vector<bool>> f(rows, vector<bool>(cols, 0));
        f[0][0] = true;    // 起点(0, 0)可达
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if((i == 0 && j == 0) || get(i) + get(j) > threshold) continue;    // 过滤条件
                if(i - 1 >= 0) f[i][j] = f[i][j] | f[i - 1][j];
                if(j - 1 >= 0) f[i][j] = f[i][j] | f[i][j - 1];
                ans += f[i][j];
            }
        }
        return ans;
    }
};

时间复杂度：O(rows * cols)，两重循环
空间复杂度：O(rows * cols)，状态转移数组f占用的空间