机器人的运动范围

http://www.nowcoder.com/questionTerminal/6e5207314b5241fb83f2329e89fdecc8

题目的主要信息：

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

举一反三：

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

JZ12. 矩阵中的路径

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

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

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

思路：

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

具体做法：

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

图示：

alt

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

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

知识点：队列

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