机器人的运动范围

题目的主要信息：

• 有一个坐标从 [0,0] 到 [rows-1,cols-1] 的方格
• 机器人每次只能走上下左右四个方向，但是行坐标和列坐标的数位之和大于 threshold 的格子不能进入
• 求从起点[0, 0]开始最多经过可以多少个格子

举一反三：

学习完本题的思路你可以解决如下题目：

JZ12. 矩阵中的路径

方法一：深度优先搜索（推荐使用）

知识点：深度优先搜索（dfs）

深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。

思路：

我们从[0,0]开始，每次选择一个方向开始检查能否访问，如果能访问进入该节点，该节点作为子问题，继续按照这个思路访问，一条路走到黑，然后再回溯，回溯的过程中每个子问题再选择其他方向，正是深度优先搜索。

具体做法：

• step 1：检查若是threshold小于等于0，只能访问起点这个格子。
• step 2：从起点开始深度优先搜索，每次访问一个格子的下标时，检查其有没有超过边界，是否被访问过了。同时用连除法分别计算每个下标的位数和，检查位数和是否大于threshold。
• step 3：若是都符合访问条件，则进行访问，增加访问的格子数，同时数组中标记为访问过了。
• step 4：然后遍历四个方向，依次进入四个分支继续访问。

图示：

Java实现代码：

public class Solution {
    //记录遍历的四个方向
    int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    //记录答案
    int res = 0;
    //计算一个数字的每个数之和
    int cal(int n){
        int sum = 0;
        //连除法算出每一位
        while(n != 0){
            sum += (n % 10);
            n /= 10;
        }
        return sum;
    }
    //深度优先搜索dfs
    void dfs(int i, int j, int rows, int cols, int threshold, boolean[][] vis){
        //越界或者已经访问过
        if(i < 0 || i >= rows || j < 0 || j >= cols || vis[i][j] == true)
            return;
        //行列和数字相加大于threshold，不可取
        if(cal(i) + cal(j) > threshold)
            return;
        res += 1;
        //标记经过的位置
        vis[i][j] = true;
        //上下左右四个方向搜索
        for(int k = 0; k < 4; k++)
            dfs(i + dir[k][0], j + dir[k][1], rows, cols, threshold, vis);
    }
    public int movingCount(int threshold, int rows, int cols) {
        //判断特殊情况
        if(threshold <= 0)
            return 1;
        //标记某个格子没有被访问过
        boolean[][] vis = new boolean[rows][cols];
        dfs(0, 0, rows, cols, threshold, vis);
        return res;
    }
}

C++实现代码：

class Solution {
public:
    //记录遍历的四个方向
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    //记录答案
    int res = 0;
    //计算一个数字的每个数之和
    int cal(int n){
        int sum = 0;
        //连除法算出每一位
        while(n){
            sum += (n % 10);
            n /= 10;
        }
        return sum;
    }
    //深度优先搜索dfs
    void dfs(int i, int j, int rows, int cols, int threshold, vector<vector<bool> >& vis){
        //越界或者已经访问过
        if(i < 0 || i >= rows || j < 0 || j >= cols || !vis[i][j])
            return;
        //行列和数字相加大于threshold，不可取
        if(cal(i) + cal(j) > threshold)
            return;
        res += 1;
        //标记经过的位置
        vis[i][j] = false;
        //上下左右四个方向搜索
        for(int k = 0; k < 4; k++)
            dfs(i + dir[k][0], j + dir[k][1], rows, cols, threshold, vis);
    }
    
    int movingCount(int threshold, int rows, int cols) {
        //判断特殊情况
        if(threshold <= 0)
            return 1;
        //标记某个格子没有被访问过
        vector<vector<bool> > vis(rows, vector<bool>(cols, true));
        dfs(0, 0, rows, cols, threshold, vis);
        return res;
    }
};

Python实现代码：

class Solution:
    def __init__(self):
        #记录遍历的四个方向
        self.dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        #记录答案
        self.res = 0
        
    #计算一个数字的每个数之和
    def cal(self, n: int) -> int:
        sum = 0
        #连除法算出每一位
        while n:
            sum += (n % 10)
            n //= 10
        return sum
    
    #深度优先搜索dfs
    def dfs(self, i: int, j: int, rows: int, cols: int, threshold: int, vis: List[List[bool]]):
        #越界或者已经访问过
        if i < 0 or i >= rows or j < 0 or j >= cols or not vis[i][j]:
            return
        #行列和数字相加大于threshold，不可取
        if self.cal(i) + self.cal(j) > threshold:
            return
        self.res += 1
        #标记经过的位置
        vis[i][j] = False
        #上下左右四个方向搜索
        for k in range(4):
            self.dfs(i + self.dir[k][0], j + self.dir[k][1], rows, cols, threshold, vis)
    
    def movingCount(self , threshold: int, rows: int, cols: int) -> int:
        #判断特殊情况
        if threshold <= 0:
            return 1
        #标记某个格子没有被访问过
        vis = [[True for i in range(cols)] for j in range(rows)]
        self.dfs(0, 0, rows, cols, threshold, vis)
        return self.res

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，其中$mm$与$nn$分别为格子的边长，深度优先搜索最坏情况下遍历格子每个位置一次
• 空间复杂度：$O(mn)O(mn)$，递归栈的最大空间为格子的大小，同时记录是否访问过的数组vis空间为$O(mn)O(mn)$

方法二：广度优先搜索（扩展思路）

知识点：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。

思路：

深度优先搜索是一条路走到底，我们还可以尝试广度优先搜索。只要遍历的时候从起点开始，依次访问与其相邻的四个方向（如果可以访问），然后再将与这四个方向相邻的节点都依次加入队列中排队等待访问。这样下来，每次访问都是一圈一圈推进，因此是广度优先搜索。

具体做法：

• step 1：检查若是threshold小于等于0，只能访问起点这个格子。
• step 2：从起点开始广度优先搜索，将其优先加入队列中等待访问，队列记录要访问的坐标。
• step 3：每次取出队列首部元素访问，进行标记，然后计数。
• step 4：然后遍历四个方向相邻的格子，检查其有没有超过边界，是否被访问过了。同时用连除法分别计算每个下标的位数和，检查位数和是否大于threshold，如果满足可以访问的条件，则将其加入队列中等待访问，同时标记访问过了。

Java实现代码：

import java.util.*;
public class Solution {
    //记录遍历的四个方向
    int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    //记录答案
    int res = 0;
    //计算一个数字的每个数之和
    int cal(int n){
        int sum = 0;
        //连除法算出每一位
        while(n != 0){
            sum += (n % 10);
            n /= 10;
        }
        return sum;
    }
    public int movingCount(int threshold, int rows, int cols) {
        //判断特殊情况
        if(threshold <= 0)
            return 1;
        //标记某个格子没有被访问过
        boolean[][] vis = new boolean[rows][cols];
        //记录答案
        int res = 0;
        Queue<ArrayList<Integer> > q = new LinkedList<ArrayList<Integer>>();
        //起点先入队列
        q.offer(new ArrayList<Integer>(Arrays.asList(0, 0)));
        vis[0][0] = true;
        while(!q.isEmpty()){
            //获取符合条件的一步格子
            ArrayList<Integer> node = q.poll();
            res += 1;
            //遍历四个方向
            for(int i = 0; i < 4; i++){
                int x = node.get(0) + dir[i][0];
                int y = node.get(1) + dir[i][1];
                //符合条件的下一步才进入队列
                if(x >= 0 && x < rows && y >= 0 && y < cols && vis[x][y] != true){
                    if(cal(x) + cal(y) <= threshold){
                        q.offer(new ArrayList<Integer>(Arrays.asList(x, y)));
                        vis[x][y] = true;
                    }
                }
            }
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    //记录遍历的四个方向
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    //计算一个数字的每个数之和
    int cal(int n){
        int sum = 0;
        //连除法算出每一位
        while(n){
            sum += (n % 10);
            n /= 10;
        }
        return sum;
    }
    
    int movingCount(int threshold, int rows, int cols) {
        //判断特殊情况
        if(threshold <= 0)
            return 1;
        //标记某个格子没有被访问过
        vector<vector<bool> > vis(rows, vector<bool>(cols, true));
        //记录答案
        int res = 0;
        queue<pair<int, int> > q;
        //起点先入队列
        q.push({0, 0});
        vis[0][0] = false;
        while(!q.empty()){
            //获取符合条件的一步格子
            auto node = q.front();
            q.pop();
            res += 1;
            //遍历四个方向
            for(int i = 0; i < 4; i++){
                int x = node.first + dir[i][0];
                int y = node.second + dir[i][1];
                //符合条件的下一步才进入队列
                if(x >= 0 && x < rows && y >= 0 && y < cols && vis[x][y]){
                    if(cal(x) + cal(y) <= threshold){
                        q.push({x, y});
                        vis[x][y] = false;
                    }
                }
            }
        }
        return res;
    }
};

Python实现代码：

class Solution:
    def __init__(self):
        #记录遍历的四个方向
        self.dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        
    #计算一个数字的每个数之和
    def cal(self, n: int) -> int:
        sum = 0
        #连除法算出每一位
        while n:
            sum += (n % 10)
            n //= 10
        return sum
    
    def movingCount(self , threshold: int, rows: int, cols: int) -> int:
        #判断特殊情况
        if threshold <= 0:
            return 1
        #标记某个格子没有被访问过
        vis = [[True for i in range(cols)] for j in range(rows)]
        #记录答案
        res = 0
        #起点先入队列
        q = [[0, 0]]
        vis[0][0] = False
        while len(q):
            #获取符合条件的一步格子
            node = q[0]
            q.pop(0)
            res += 1
            #遍历四个方向
            for i in range(4):
                x = node[0] + self.dir[i][0]
                y = node[1] + self.dir[i][1]
                #符合条件的下一步才进入队列
                if x >= 0 and x < rows and y >= 0 and y < cols and vis[x][y]:
                    if self.cal(x) + self.cal(y) <= threshold:
                        q.append([x, y])
                        vis[x][y] = False
        return res

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，其中$mm$与$nn$分别为格子的边长，广度优先搜索最坏情况下遍历格子每个位置一次
• 空间复杂度：$O(mn)O(mn)$，队列的最大空间为格子的大小，同时记录是否访问过的数组vis空间为$O(mn)O(mn)$