java - 打印迷宫中最短路径的长度

Question

我正在尝试让 Java 程序在迷宫中找到最短路线并打印这条路的长度。

.是一种方式，'x' 是障碍。

如果我输入

....xxx.
x.x....x
xxx.....
x......x
...xxxxx
........
xxx.....
xx......

输出是无限的:

0, 0
0, 1
1, 1
0, 1
1, 1
0, 1
1, 1
0, 1
1, 1
0, 1
1, 1
0, 1
1, 1
0, 1
...

并且发生 java.lang.StackOverflowError。

正确的输出必须是

0, 0
0, 1
1, 1
0, 1
0, 2
0, 3
1, 3
2, 3
3, 3
3, 4
3, 5
3, 6
3, 5
3, 4
3, 3
3. 2
4, 2
5, 2
5, 3
6, 3
7, 3
7, 4
7, 5
7, 6
7, 7
16

如何修改我的代码并获得正确答案？ 或者我应该使用什么算法来制作新代码？ 我很困惑..

试了很多次都没有得到正确答案T_T 请帮助我

import java.util.Scanner;

public class ShortestMazeWay
{
    static int count=0;
    static int[] result = new int[10000]; // save the move direction
    static int[][] find = new int[8][8];
    static int[][] maze = new int[8][8]; //  0 = can go, 1 = can not go

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        for(int i=0; i<8; i++)
        {
            String str = sc.nextLine();

            for(int j=0; j<8; j++)
            {
                if(str.charAt(j)=='.')
                    maze[i][j]=0;
                else
                    maze[i][j]=1;
            }
        }

        find(0, 0); // start from (0, 0)
    }

    static void find(int i, int j)
    {
        find[i][j] = 1; // 0 = can go, 1 = can not go
        System.out.println(i+", "+j); // to check the way

        if(i==7 && j==7) // the end point is (7, 7)
            System.out.println(count);

        else
        {
            count++;

            if(i+1<8 && maze[i+1][j]!=1 && find[i+1][j]==0) // ↓ 
            {
                result[count] = 1;
                find[i][j] = 0;
                find(i+1, j);
            }

            else if(j+1<8 && maze[i][j+1]!=1 && find[i][j+1]==0) // →
            {
                result[count] = 2;
                find[i][j] = 0;
                find(i, j+1);
            }

            else if(i-1>=0 && maze[i-1][j]!=1 && find[i-1][j]==0) // ↑
            {
                if(result[count-1]==2) // if moved ↓ in previous step,
                    count--; // go back to previous position
                else
                    result[count] = 3;

                find[i][j] = 0;
                find(i-1, j);
            }

            else if(j-1>=0 && maze[i][j-1]!=1 && find[i][j-1]==0) // ←
            {
                if(result[count-1]==1) // if moved → in previous step,
                    count--; // go back to previous position
                else
                    result[count] = 4;

                find[i][j] = 0;
                find(i, j-1);
            }
        }
    }
}

Answer 1

在 . 上行走时，您需要确保不要踩到您已经踩过的 .。

一种方法是留下面包屑，例如将 . 更改为 *，并记得将其改回 '.'当你回溯时。

示例:方向顺序为上、右、下、左 :

*...xxx. 1  **..xxx. 2  ***.xxx. 3  ****xxx. 4  ****xxx. 5  ****xxx. 6
x.x....x    x.x....x    x.x....x    x.x....x    x.x*...x    x.x**..x
xxx.....    xxx.....    xxx.....    xxx.....    xxx.....    xxx.....
x......x    x......x    x......x    x......x    x......x    x......x
...xxxxx    ...xxxxx    ...xxxxx    ...xxxxx    ...xxxxx    ...xxxxx
........    ........    ........    ........    ........    ........
xxx.....    xxx.....    xxx.....    xxx.....    xxx.....    xxx.....
xx......    xx......    xx......    xx......    xx......    xx......

****xxx. 7  ****xxx. 8  ****xxx. 9  ****xxx. 10 ****xxx. 11 ****xxx. 12
x.x***.x    x.x****x    x.x****x    x.x****x    x.x****x    x.x****x
xxx.....    xxx.....    xxx...*.    xxx...**    xxx...*.    xxx...*.
x......x    x......x    x......x    x......x    x.....*x    x....**x
...xxxxx    ...xxxxx    ...xxxxx    ...xxxxx    ...xxxxx    ...xxxxx
........    ........    ........    ........    ........    ........
xxx.....    xxx.....    xxx.....    xxx.....    xxx.....    xxx.....
xx......    xx......    xx......    xx......    xx......    xx......

****xxx. 13 ****xxx. 14 ****xxx. 15 ****xxx. 16 ****xxx. 17 ****xxx. 18
x.x****x    x.x****x    x.x****x    x.x****x    x.x****x    x.x****x
xxx..**.    xxx.***.    xxx.***.    xxx.***.    xxx****.    xxx.***.
x....**x    x....**x    x...***x    x..****x    x..****x    x.*****x
...xxxxx    ...xxxxx    ...xxxxx    ...xxxxx    ...xxxxx    ...xxxxx
........    ........    ........    ........    ........    ........
xxx.....    xxx.....    xxx.....    xxx.....    xxx.....    xxx.....
xx......    xx......    xx......    xx......    xx......    xx......

请注意它如何在第 10 步和第 11 步之间回溯，然后在第 17 步和第 18 步之间再次回溯。

记住:第一次到达终点不一定是最短路线。您必须尝试所有步骤的所有组合，并记住找到的最短路径，而不仅仅是找到的第一条路径。

根据上面使用的方向顺序，这里有一些完整路线的例子:

First       Shortest    Shortest    Last        Longest
****xxx.    ****xxx.    ****xxx.    ****xxx.    ****xxx.
x.x****x    x.x*...x    x.x*...x    x.x*...x    x.x****x
xxx.***.    xxx*....    xxx*....    xxx*....    xxx.***.
x.*****x    x.**...x    x.**...x    x***...x    x.*****x
..*xxxxx    ..*xxxxx    ..*xxxxx    **.xxxxx    ***xxxxx
..******    ..******    ..***...    ****....    ********
xxx....*    xxx....*    xxx.***.    xxx*....    xxx*****
xx.....*    xx.....*    xx....**    xx.*****    xx.*****

因此，因为每次到达终点时都必须记住所走的完整路线，所以堆栈实现比当前使用的递归实现要好。

更新:优化

对解决问题的方法有了新的想法，无需回溯，这意味着它应该更快。

用步数替换面包屑，即到达该位置的(最少)步数。

用 -1 初始化 maze 用于阻塞 (x) 和 Integer.MAX_VALUE 用于打开 (.)，然后这样做:

walk(maze, 0, 0, 1);

private static void walk(int[][] maze, int y, int x, int step) {
    if (y >= 0 && y < 8 && x >= 0 && x < 8 && maze[y][x] > step) {
        maze[y][x] = step;
        walk(maze, y - 1, x, step + 1);
        walk(maze, y + 1, x, step + 1);
        walk(maze, y, x + 1, step + 1);
        walk(maze, y, x - 1, step + 1);
    }
}

结果是这样的迷宫:

 1   2   3   4  XX  XX  XX  .. <-- Unreachable
XX   3  XX   5   6   7   8  XX
XX  XX  XX   6   7   8   9  10
XX   9   8   7   8   9  10  XX
11  10   9  XX  XX  XX  XX  XX
12  11  10  11  12  13  14  15
XX  XX  XX  12  13  14  15  16
XX  XX  14  13  14  15  16  17

现在您可以通过从末尾 (17) 开始追踪找到最短路径，一直到较小的数字，直到回到起点 (1) .