недавно я пытался поработать над рекурсивным кодом лабиринта, который возвращает кратчайший путь в лабиринте.Если нет пути через лабиринт, код вернет -1.
Например, для доски:
W-S-
----
--X-
Где S - начало лабиринта, W - стена, X - желаемый пункт назначения и - - доступная точка пути.Вывод будет: 2
Для платы:
-SW
-W-
W-X
вывод будет -1
Все это выполняется через класс платы, которыйпринимает строку и размеры лабиринта, функцию проверки, которая возвращает кратчайший путь, и функцию win, которая возвращает кратчайший путь, или -1, если пути нет.Однако, когда я запускаю свой код, я получаю выходные данные с отрицательным значением 1 для первого примера и с выходным значением 1 для второго примера.
Мой код:
Класс платы:
class Board
{
private char[][] board;
private int maxPath = 9999;
public Board(int rows, int cols, String line)
{
char[][] board1 = new char[rows][cols];
int z = 0;
for(int x = 0; x < rows; x++) {
for(int y = 0; y < cols; y++) {
board1[x][y] = line.charAt(z);
z++;
}
}
board = board1;
}
/** returns the length of the longest possible path in the Board */
public int getMaxPath()
{
return maxPath;
}
public void display()
{
if(board==null)
return;
System.out.println();
for(int a = 0; a<board.length; a++)
{
for(int b = 0; b<board[0].length; b++)
{
System.out.print(board[a][b]);
}
System.out.println();
}
}
/**
* calculates and returns the shortest path from S to X, if it exists
* @param r is the row of "S"
* @param c is the column of "S"
*/
public int check(int r, int c)
{
if(r<0||r > board.length-1||c<0||c>board[0].length-1) {
return maxPath;
}
if(board[r][c] == '*') {
return maxPath;
}
if(board[r][c] == 'W') {
return maxPath;
}
if(board[r][c] == 'X') {
return 0;
}
if(board[r][c] == '-') {
board[r][c] = '*';
}
int up = 1 + check(r-1,c);
int down = 1 + check(r+1,c);
int left = 1 + check(r,c-1);
int right = 1 + check(r,c+1);
board[r][c] = '-';
if(up < down) {
if(up < left) {
if(up < right) {
return up;
}
else {
return right;
}
}
else {
if(left < right) {
return left;
}
else {
return right;
}
}
}
else {
if(down < left) {
if(down < right) {
return down;
}
else {
return right;
}
}
else {
if(left < right) {
return left;
}
else {
return right;
}
}
}
}
/**
* precondition: S and X exist in board
* postcondition: returns either the length of the path
* from S to X, or -1, if no path exists.
*/
public int win()
{
int x = 0;
int y = 0;
int z = 0;
int startRow = 0;
int startCol = 0;
while( x < board.length && z == 0) {
while(y < board[0].length && z == 0) {
if(board[x][y] == 'S') {
z++;
startRow = x;
startCol = y;
}
y++;
}
x++;
}
System.out.println(startRow + " " + startCol);
if(check(startRow,startCol) < maxPath) {
return check(startRow,startCol);
}
else if (check(startRow,startCol) == maxPath) {
return 1;
}
else {
return -1;
}
}
Контрольные примеры:
public static void main(String[] args)
{
Board b = null;
b = new Board(3,4,"W-S-------X-");
b.display();
System.out.println("Shortest path is " + b.win()); //2
b = new Board(4,3,"S-W-----X-W-");
b.display();
System.out.println("Shortest path is " + b.win()); //4
b = new Board(3,4,"X-WS--W-W---");
b.display();
System.out.println("Shortest path is " + b.win()); //7
b = new Board(3,5,"W--WW-X----SWWW");
b.display();
System.out.println("Shortest path is " + b.win()); //1
b = new Board(3,3,"-SW-W-W-X"); //no path exists
b.display();
System.out.println("Shortest path is " + b.win()); //-1
b = new Board(5,7,"-W------W-W-WX--S----W----W-W--W---"); //Example Board 1
b.display();
System.out.println("Shortest path is " + b.win()); //5
b = new Board(4,4,"-WX--W-W-WW-S---"); //Example Board -1
b.display();
System.out.println("Shortest path is " + b.win()); //5
//what other test cases should you test?
}
Желаемые выходы:
W-S-
----
--X-
Shortest path is 2
S-W
---
--X
-W-
Shortest path is 4
X-WS
--W-
W---
Shortest path is 7
W--WW
-X---
-SWWW
Shortest path is 1
-SW
-W-
W-X
Shortest path is -1
-W-----
-W-W-WX
--S----
W----W-
W--W---
Shortest path is 5
-WX-
-W-W
-WW-
S---
Shortest path is -1
Мои неправильные выводы:
W-S-
----
--X-
Shortest path is -1
S-W
---
--X
-W-
Shortest path is 1
X-WS
--W-
W---
Shortest path is -1
W--WW
-X---
-SWWW
Shortest path is -1
-SW
-W-
W-X
Shortest path is 1
-W-----
-W-W-WX
--S----
W----W-
W--W---
Shortest path is 1
-WX-
-W-W
-WW-
S---
Shortest path is 1
Мои новые, в основном правильные выводы:
W-S-
----
--X-
0 2
Shortest path is 2
S-W
---
--X
-W-
0 0
Shortest path is 4
X-WS
--W-
W---
0 3
Shortest path is 7
W--WW
-X---
-SWWW
0 0
Shortest path is 1
-SW
-W-
W-X
0 1
Shortest path is -1
-W-----
-W-W-WX
--S----
W----W-
W--W---
0 0
Shortest path is 9
-WX-
-W-W
-WW-
S---
0 0
Shortest path is -1
Может кто-нибудь объяснить, что я делаю неправильно (только между моими новыми выходами и желаемыми выходами) и какЯ могу это исправить?
РЕДАКТИРОВАТЬ: Спасибо, Питер и MRB, я реализовал ваши предложения и обновил мой код, чтобы соответствовать этому!