recursion - 如果存在解决方案，迷宫问题的复杂性（应用回溯算法）

Question

这是解决方案：使用递归树方法，看起来它应该是指数的，即 4 次幂 n。但解决它并不清楚。就像人们在采访中的描述一样。任何帮助表示赞赏。

class Solution {
    public static boolean hasPath(int[][] maze, int[] start, int[] destination) {
        boolean result = false;
        result = moveNext(maze, start[0], start[1], destination);
        return result;
    }
    public static boolean moveNext(int[][] graph, int i, int j, int[] destination) {
        if (i < 0 || i == graph.length ||
                j < 0 || j == graph[0].length ||
                graph[i][j] == 1)
           return false;
        graph[i][j] = 1;
        if (i == destination[0] && j == destination[1])
           return true;

        return moveNext(graph, i, j + 1, destination)
               || moveNext(graph, i + 1, j, destination)
               || moveNext(graph, i, j - 1, destination) 
               || moveNext(graph, i - 1, j, destination);
    }

    public static void main(String args[]) {
        int[][] maze = {
            { 0, 1, 1, 1 },
            { 1, 0, 1, 0 },
            { 1, 0, 1, 1 },
            { 0, 0, 0, 0 }
        };
        int start[] = { 0, 0 };
        int destination[] = { 3, 3 };
        System.out.println(hasPath(maze, start, destination));
    }
}

标签： recursiontime-complexityrecursive-backtracking