我正在尝试让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 Plz帮助我
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);
}
}
}
}
Andreas.. 5
走路时.,你需要确保不要.踩到已经踩到的那个.
一种方法是离开面包屑,例如将其更改.为a *,并记住将其更改为"." 当你回溯.
例如:方向顺序是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使用-1for blocked(x)和Integer.MAX_VALUEopen(.)初始化,然后执行以下操作:
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
现在你可以通过从end(17)跟踪到最低路径来找到最短路径,直到你回到起点(1).
走路时.,你需要确保不要.踩到已经踩到的那个.
一种方法是离开面包屑,例如将其更改.为a *,并记住将其更改为"." 当你回溯.
例如:方向顺序是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使用-1for blocked(x)和Integer.MAX_VALUEopen(.)初始化,然后执行以下操作:
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
现在你可以通过从end(17)跟踪到最低路径来找到最短路径,直到你回到起点(1).
京公网安备 11010802040832号 | 京ICP备19059560号-6 