gpt4 book ai didi

java - 使用递归解决二维数组迷宫

转载 作者:行者123 更新时间:2023-12-02 10:43:07 24 4
gpt4 key购买 nike

我正在编写一段代码来读取带有迷宫的 txt 文件。然后使用递归解决该迷宫。

我已经完全重写了我的代码好几次,但似乎我的代码没有从起点移动。我不知道为什么要这样做。

public static void main(String[] args){
//Read in maze file...

//Find starting point
int startRow = 0;
int startColumn = 0;
for(int i = 0; i <maze[0].length; i++)
{
if(maze[6][i] == 's')
{
startRow = 6;
startColumn = i;
}
}

if(solve(maze,startRow,startColumn))
{
System.out.println("Success");

for(int r = 0; r < 7; r++)
{
for(int c = 0; c < 20; c++)
{
System.out.print(maze[r][c]);
}
System.out.println();
}
}
else
{
System.out.println("Fail");

for(int r = 0; r < 7; r++)
{
for(int c = 0; c < 20; c++)
{
System.out.print(maze[r][c]);
}
System.out.println();
}
}
}

public static boolean solve(char[][] maze, int row, int column)
{
boolean success = false;
if(valid(maze, row, column))
{
maze[row][column] = 'v'; //mark as visited

if (maze[row][column] == 'f') //check for finish
success = true;
else
{
success = solve(maze, row - 1, column); //north
if(!success)
success = solve(maze, row, column + 1); //west
if(!success)
success = solve(maze, row, column - 1); //east
if(!success)
success = solve(maze, row + 1, column); //south
}
if(success) //mark as path
maze[row][column] = 'p';
}
return success;
}
public static boolean valid(char[][] maze, int row, int column)
{
boolean a = false;
if(row >= 0 && row < maze.length && column >= 0 && column < maze[0].length)
if (maze[row][column] == ' ')
a = true;
return a;
}

}

我使用 7x20 文本文件进行测试:

xxxxxxxxxxxxxxxxxxfx
x x xxxx x
x xxxxx xxxxx xx x
x xxxxx xxxxxxx xx x
x xx xx x
x xxxxxxxxxx xx x
xxxxxxxxxxxxsxxxxxxx

“x”=墙

's' = 开始

“f”=完成

我的输出:

Fail
xxxxxxxxxxxxxxxxxxfx
x x xxxx x
x xxxxx xxxxx xx x
x xxxxx xxxxxxx xx x
x xx xx x
x xxxxxxxxxx xx x
xxxxxxxxxxxxsxxxxxxx

最佳答案

您的搜索永远不会开始,因为您的 valid 方法将起点 s 报告为无效。

快速解决方法是更改​​:

if (maze[row][column] == ' ')
a = true;

if (maze[row][column] == ' ' || maze[row][column] == 's')
a = true;

另一个问题是您在检查之前覆盖了访问的完成单元格:

maze[row][column] = 'v';  //mark as visited

if (maze[row][column] == 'f') //check for finish
success = true;

您需要重构您的求解方法,使其看起来像这样:

public static boolean solve(char[][] maze, int row, int column)
{
boolean success = false;

if (maze[row][column] == 'f') //check for finish
success = true;
else if(valid(maze, row, column))
{
maze[row][column] = 'v'; //mark as visited

success = solve(maze, row - 1, column); //north
if(!success)
success = solve(maze, row, column + 1); //west
if(!success)
success = solve(maze, row, column - 1); //east
if(!success)
success = solve(maze, row + 1, column); //south

if(success) //mark as path
maze[row][column] = 'p';
}
return success;
}

通过这些更改,您的代码可以完美运行:

Success
xxxxxxxxxxxxxxxxxxfx
x xpppppppxxxxpx
x xxxxxpxxxxxpppxxpx
x xxxxxpxxxxxxxpxxpx
x ppppppxxpxxpx
x xxxxxxxxxxpxxppppx
xxxxxxxxxxxxpxxxxxxx

关于java - 使用递归解决二维数组迷宫,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52789107/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com