我试图让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_TPlz帮我
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);
}
}
}
}
在.上行走时，需要确保没有踩到已经踩过的.。
一种方法是留下一个面包屑，例如将.改为*，并记住将其改回"当你回头的时候。
示例：方向顺序为up、right、down、left:
*...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.*****
因此，因为每次到达终点时都必须记住完整的路线，所以堆栈实现比当前使用的递归实现要好。
更新：优化
对一种不用回溯就能解决问题的方法有了新的想法，这意味着它应该更快。
将面包屑替换为步数，即到达该位置的（最少）步数。
初始化maze，-1表示阻塞（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）来找到最短路径。