在迷宫中改良的大鼠

Question

在接受采访时我问过你.你给我的矩阵填充了"1"和"0"."1"表示你可以使用单元格,"0"表示单元格被阻挡.你可以向4个方向移动左,右,上,下每次你向上或向下移动它都会花费你1美元.向左或向右移动不会增加成本.所以你必须编写一个代码来检查是否可以达到目的地索引( x,y)从(0,0)开始.如果是,则打印最低成本,否则打印"-1".

我无法计算成本.这是我的代码

public class Test {

    /**
     * @param args the command line arguments
     */
    static int dest_x = 0;
    static int dest_y = 0;
    static int cost = 0;
    static int m = 0;
    static int n = 0;

    public static void main(String[] args) {
        // TODO code application logic here
        Scanner in = new Scanner(System.in);
        Test rat = new Test();
        int maze[][] = {
                {1, 1, 1, 1},
                {1, 1, 1, 0},
                {1, 1, 1, 1},
                {0, 0, 1, 1}
        };
        dest_x = in.nextInt();
        dest_y = in.nextInt();
        m = in.nextInt();
        n = in.nextInt();
        if (rat.solveMaze(maze))
            System.out.println("YES");

        else {
            System.out.println("NO");
        }
        System.out.println("cost = " + cost);
    }

    boolean isSafe(int maze[][], int x, int y) {
        // if (x,y outside maze) return false
        return (x >= 0 && x < m && y >= 0 &&
                y < n && maze[x][y] == 1);
    }

    boolean solveMaze(int maze[][]) {
        int sol[][] = {{0, 0, 0, 0},
                {0, 0, 0, 0},
                {0, 0, 0, 0},
                {0, 0, 0, 0}
        };

        if (!solveMazeUtil(maze, 0, 0, sol)) {
            return false;
        }
        return true;
    }

    boolean solveMazeUtil(int maze[][], int x, int y, int sol[][]) {
        // if (x,y is goal) return true
        if (x <= dest_x || y <= dest_y)
            if (x == dest_x && y == dest_y) {
                sol[x][y] = 1;
                return true;
            } else if (sol[x][y] == 1) {
                return false;
            }

            // Check if maze[x][y] is valid
            else if (isSafe(maze, x, y)) {
                // mark x,y as part of solution path
                sol[x][y] = 1;

                // Move forward in x direction 
                if (solveMazeUtil(maze, x + 1, y, sol)) {
                    //System.out.println("here at x+1 x = " + x  + " y = " + y);
                    return true;
                }

                // Move down in y direction 
                if (solveMazeUtil(maze, x, y + 1, sol)) {
                    //System.out.println("here at y+1 x = " + x  + " y = " + y);
                    cost++;
                    return true;
                }
                cost--;
                if (solveMazeUtil(maze, x - 1, y, sol)) {
                    // System.out.println("here at x-1 x = " + x  + " y = " + y);  
                    return true;
                }
                if (solveMazeUtil(maze, x, y - 1, sol)) {
                    //System.out.println("here at y-1 x = " + x  + " y = " + y);  
                    cost++;
                    return true;
                }
                cost--;
                /* If no solution then
                   BACKTRACK: unmark x,y as part of solution
                   path */
                sol[x][y] = 0;
                return false;
            }
        return false;
    }
}

Answer 1

将迷宫变成有向图并解决最短路径问题

1. 标记为 的单元格"1"是节点（标记为"0"应被忽略）
2. 如果我们可以从一个单元（节点）移动到另一个单元（节点），则用有向边将它们连接起来；将成本（0或）放在边上（请注意，我们有一个多重图：两个节点可以与两条1不同的边连接）。
3. 最后，借助Dijkstra 算法找到所需节点之间的最短路径（即最小成本）。