Java 回溯法 求矩阵路径

问题：从矩阵左上角到右下角有多少条路径，只能向右或向下走。矩阵中的元素由1和0组成，1代表可以通过，0代表障碍物。
两种方法，本质上没有区别
方法一

import java.util.Scanner;

public class Demo111 {
    private static int count = 0;  //定义全局变量，记录矩阵数目
    private static boolean[][] visited;

    public static void main(String[] args) {
        int[][] mat = {{1, 0, 0}, {1, 1, 1}, {1, 1, 1}};
        visited = new boolean[3][3];
        recur(mat, 0, 0);
        System.out.println(count);
    }

    private static boolean recur(int[][] mat, int i, int j) {
        if (i < 0 || i >= mat.length || j < 0 || j >= mat[0].length || visited[i][j] ||mat[i][j] == 0) {
            return false;  
        }
        if(i==mat.length-1 && j ==mat[0].length-1){
            count++;
            return true;
        }
        visited[i][j] = true;
        boolean res = recur(mat, i, j+1);
        res = recur(mat, i+1,j) || res; //注意，如果使用boolean类型做返回值，需要将两次递归分开写，因为||特性是如果第一个表达式为true则不会计算第二个表达式
        visited[i][j] = false;
        return res;
    }
}

方法二

public class Demo112 {
    private static boolean[][] visited;

    public static void main(String[] args) {
        int[][] mat = {{1, 0, 0}, {1, 1, 1}, {1, 1, 1}};
        visited = new boolean[3][3];
        int result = recur(mat, 0, 0);
        System.out.println(result);
    }

    private static int recur(int[][] mat, int i, int j) {
        if (i < 0 || i >= mat.length || j < 0 || j >= mat[0].length || visited[i][j] || mat[i][j] == 0) {
            return 0;
        }
        if (i == mat.length && j == mat[0].length) {
            return 1;
        }

        visited[i][j] = true;
        int res = recur(mat, i, j + 1) + recur(mat, i + 1, j);
        visited[i][j] = false;
        return res;
    }
}

附加：
剑指offer12 矩阵中的路径
也可以用类似上面的思想去做，回溯+剪枝（参考评论区K神做法）

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                boolean re = recur(board, word, i, j, 0);
                if(re == true){
                    return true;
                }
            }
        }
        return false;
    }
    public static  boolean recur(char[][] board, String word,int i, int j,int k){
        if(i<0||i>board.length-1||j<0||j>board[0].length-1||word.charAt(k)!=board[i][j]){
            return false;
        }
        if(k==word.length()-1){
            return true;
        }

        char temp = board[i][j];
        board[i][j] = ' ';
        boolean res = recur(board, word, i+1, j, k+1) || recur(board, word, i, j+1, k+1) || recur(board, word, i-1, j, k+1) || recur(board, word, i, j-1, k+1);
        board[i][j] = temp;
        return res;
    }
}