剑指 Offer 13. 机器人的运动范围&剑指 Offer 12. 矩阵中的路径---dfs题目的应对策略

列举剑指 Offer有关dfs的两道初级题目，来谈谈这种题的自己的心得。

剑指 Offer 13. 机器人的运动范围

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] b=new boolean[m][n];
        return dfs(b,0,0,k);
    }
    public int dfs(boolean[][] b,int i,int j,int k){
    //判断错误的情况 
    //i>=b.length||j>=b[0].length    超界错误
    //(i/10+i%10+j/10+j%10)>k i                j的个位十位加一起超过了k错误
    //b[i][j]==true)                           这个格子已经走过错误
        if(i>=b.length||j>=b[0].length||(i/10+i%10+j/10+j%10)>k||b[i][j]==true) return 0;
        b[i][j]=true;//当前格子已经来过了
        //因为我们从(0.0)开始，所以不用考虑左面和上面
        return dfs(b,i+1,j,k)+dfs(b,i,j+1,k)+1;
        
    }}

大体思路就是 一个递归 ，错误情况不计数，正确情况计数并且把盒子标记。然后一直像右面和下面调用dfs递归回溯。(i/10:十位，i%10:个位)

剑指 Offer 12. 矩阵中的路径-

对评论区大佬的答案进行分析总结：

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }

        char[] chars = word.toCharArray();
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                //因为要求格子不能重复利用且不能回滚所以这道题的visited不可以重复利用，就需要对每个点进行遍历
                if (dfs(board, chars, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] chars, boolean[][] visited, int i, int j, int start) {
        //超界或者格子被踩过或者格子不是对应字母返回错误
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length 
                || chars[start] != board[i][j] || visited[i][j]) {
            return false;
        }
        //当word恰好匹配
        if (start == chars.length - 1) {
            return true;    
        }
        //标记该格子已经被匹配
        visited[i][j] = true;
        boolean ans = false;
        ans = dfs(board, chars, visited, i + 1, j, start + 1) 
           || dfs(board, chars, visited, i - 1, j, start + 1)
           || dfs(board, chars, visited, i, j + 1, start + 1)
           || dfs(board, chars, visited, i, j - 1, start + 1);
        //匹配完将格子复原到没有踩过的形态
        visited[i][j] = false;
        return ans;
    }
}

大体思路：

• 判断数组是否为空
• 对每一个格子进行匹配，寻找相应的路径

对visited 判断该格子是否被占用的使用和思考
如果格子不能被重复使用的时候，需要使用 visited来辅助我们的判断，而辅助判断后需不需要复原，就分为两种情况
1.像第一道题，需要我们需要的格子个数，允许我们对路线回滚，且只遍历一遍矩阵就可以了，就不需要将visited归位
2.第二道题，因为我们需要对每一个格子进行路线寻找，visited不重置就会影响我们对路线的判断，所以上一个几点结束后要重置visited