矩阵中的路径+机器人的运动范围题目分析

“矩阵中的路径” 和 "机器人的运动范围"是剑指offer的倒数第2,3道题目，因为这两道题思路类似，就放在一起说。

矩阵中的路径(leetcode版本)

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,“b”,“c”,“e”],
[“s”,“f”,“c”,“s”],
[“a”,“d”,“e”,“e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例 1：
输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

示例 2：
输入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
输出：false
提示：
1 <= board.length <= 200
1 <= board[i].length <= 200

解题思路：
这个题是路径规划问题，给定一个矩阵地图和一条路，判断这个地图里面是否存在一条路径和题目所给这条路完全匹配。
既然是路径规划，很容易想到用到递归+回溯，因为每个矩阵中的每个格子可能被多条不同的路径经过，所以每条路径用完这个格子之后要将其复原，因此需要一个二维bool型数组，来标记格子是否被走过，这是回溯法的常规套路。
有了上面的思路，我们就来进行匹配。题目给定一个字符串word，那我们就从矩阵的第一个位置( board[0][0] )开始匹配，每次走完一个字符，下一个字符我们有四种选择：往上，往下，往左，往右。
所以递归主体就要包含这四种情况，但是别忘了上面说的，走一个字符就要做一个标记，也即是二维数组的该位置标记，递归完后进行复原，给其他路径去用。
那递归主体确定了之后，就要进行边界判断，因为递归也就包含两部分：边界+主体。那边界就很简单了，既然上面分析了一个字符有四种走法，那肯定不能跑出界，也不能有小于0的情况，并且！每个路径用过的格子 本路径不能再用，也即是每个格子在每条路径中只能用一次（这是题目条件）。
因此，总结一下边界条件：① 越界 ② 走过的格子不能再走 ③匹配过程中某个值不相等，那就直接return false。
如果上面的情况都没有发生，那就说明匹配过程很顺利，直接走完题目所给的路径，那么return true。
下面开始写代码：用一个变量index跟踪题目所给的路径，逐个字符匹配，当index = word.length( )时，return true;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(word.size() <= 0){
            return true;
        }
        vector<vector<bool>> vis(board.size(), vector<bool>(board[0].size(), false));  //标记数组
        for(int i = 0; i < board.size(); ++i){
            for(int j = 0; j < board[i].size(); ++j){
                if(dfs(board, word, i, j, 0, vis)){ //逐个字符匹配
                    return true;
                }
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>> &board, string &word, int x, int y, int index, vector<vector<bool>> &vis){
        if(index == word.length()){
            return true;   //走完题目所给的路径，匹配成功
        }
        if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || vis[x][y]){
            return false;  //越界&该路径用过的格子 判断
        }
        if(board[x][y] != word[index]){
            return false;  //值不相等判断
        }
        
        //下面是递归+回溯，也就是匹配的过程
        vis[x][y] = true;  //用了就做标记
        bool res = dfs(board, word, x + 1, y, index + 1, vis) || dfs(board, word, x - 1, y, index + 1, vis)
        || dfs(board, word, x, y + 1, index + 1, vis) || dfs(board, word, x, y - 1, index + 1, vis);
        vis[x][y] = false; //复原，给其他路径用
        return res;
    }
};

这个思路是比较容易想的，不会太复杂。但是在leetcode中需要注意超时的情况，一开始我传参的时候，第一个参数board没有传引用，直接传值，结果一直超时，在时间复杂度较大的时候，一定要尽量优化，传引用省去了值拷贝的过程，因此可以accept。

机器人运动范围(leetcode版本)

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

解题思路：
这个题和上一个“矩阵中的路径”比较类似，最重要的不同点是上一个题是典型的路径规划问题，需要用到回溯法（因为可能多条路径经过同一个点），但是这个题不一样，他要的是我们去判断每一个点是不是满足条件（和<k），满足的话就总数+1，不满足就过，所以也就是说：每个格子只需要走一次，那既然每个格子只走一次，就不需要回溯了，只需要每个格子走过就做一个标记。终止条件中遇到这个标记就直接return，因为代表这个格子走过了，不能再走了。
并且，每个格子走完之后，下一个格子也是有四种选择：往上，往下，往左，往右，所以这个题和上一个题目基本一样，最大的不同点就是上一个题需要回溯，这个题并不用。因为这个题的要求是找出所有满足条件的格子，那一个格子就只需要走一次，满足条件就+1，不满足就过了， 不存在路径的选择。
代码：

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> vis(m, vector<bool>(n, false)); //标记数组
        sum = 0;
        dfs(m, n, k, 0, 0, vis);
        return sum;
    }
    int calculate(int x){  //计算数字的所有位数之和
        int Sum = 0;
        while(x > 0){
            Sum += x % 10;
            x /= 10;
        }
        return Sum;
    }
    void dfs(int m, int n, int k, int x, int y, vector<vector<bool>> &vis){
        if(x < 0 || x >= m || y < 0 || y >= n || vis[x][y]){
            return;   //越界&格子只能用一次 判断
        }
        if(calculate(x) + calculate(y) > k){
            return;   //和 < K 不满足
        }
        
        vis[x][y] = true;  //做标记
        ++sum;   //可用格子+1
        dfs(m, n, k, x + 1, y, vis);  //往下
        dfs(m, n, k, x - 1, y, vis);  //往上
        dfs(m, n, k, x, y + 1, vis);  //往右
        dfs(m, n, k, x, y - 1, vis);  //往左
    }
private:
    int sum;
};