1
我想写一个给予迷宫的程序，并试图找到出路。 M是入口，E是出口，1是墙壁，0是通道。它应该找到每个路径并将P放在路径中。它应该找到所有可用的路径。现在它找到了路径的一部分。如何找到所有可用的迷宫路径？
下面是代码：
public class Maze
{
private int size;
private String[][] board;
private int total; //# of boards
private int eX;
private int eY;
private int mX;
private int mY;
public Maze(int size, String[][] board)
{
this.size = size;
this.board = board;
total = 0;
}
private void find(String c)
{
int x=0, y=0;
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size; j++)
{
if(board[i][j].equals(c))
{
x = i;
y = j;
}
}
}
if(c.equals("M"))
{
mX = x;
mY = y;
}
else if(c.equals("E"))
{
eX = x;
eY = y;
}
}
public void findPath()
{
find("M");
find("E");
findNext(mX, mY);
}
public void findNext(int x, int y)
{
String last = board[x][y];
if(board[x][y].equals("P")) board[x][y] = "1";
board[x][y] = "P";
if(rightAvailability(x,y))
{
findNext(x+1, y);
}
else if(leftAvailability(x,y))
{
findNext(x-1, y);
}
else if(aboveAvailability(x,y))
{
findNext(x, y+1);
}
else if(belowAvailability(x,y))
{
findNext(x, y-1);
}
else
{
total++;
printBoard();
}
board[x][y]= last;
}
public boolean rightAvailability(int x, int y)
{
if(x+1 >= size) return false;
else if(board[x+1][y].equals("1")) return false;
else if(board[x+1][y].equals("P")) return false;
else return true;
}
public boolean leftAvailability(int x, int y)
{
if(x-1 < 0) return false;
else if(board[x-1][y].equals("1")) return false;
else if(board[x-1][y].equals("P")) return false;
else return true;
}
public boolean aboveAvailability(int x, int y)
{
if(y+1 >= size) return false;
else if(board[x][y+1].equals("1")) return false;
else if(board[x][y+1].equals("P")) return false;
else return true;
}
public boolean belowAvailability(int x, int y)
{
if(y-1 < 0) return false;
else if(board[x][y-1].equals("1")) return false;
else if(board[x][y-1].equals("P")) return false;
else return true;
}
public void printBoard()
{
System.out.println("The board number " +total+ " is: ");
for(int i=0; i< size; i++)
{
for(int j=0; j< size; j++)
{
if((i==mX) && (j==mY))
{
System.out.print("M");
}
else if((i==eX) && (j==eY))
{
System.out.print("E");
}
else if(board[i][j].equals("1"))
{
System.out.print("1");
}
else if(board[i][j].equals("0"))
{
System.out.print("0");
}
else
{
System.out.print("P");
}
}
System.out.println();
}
}
}
下面是测试仪：
public class MazeTester
{
public static void main(String[] args)
{
int size = 11;
String[][] board = new String[][]
{
{"1","1","1","1","1","1","1","1","1","1","1"},
{"1","0","0","0","0","0","1","0","0","0","1"},
{"1","0","1","0","0","0","1","0","1","0","1"},
{"E","0","1","0","0","0","0","0","1","0","1"},
{"1","0","1","1","1","1","1","0","1","0","1"},
{"1","0","1","0","1","0","0","0","1","0","1"},
{"1","0","0","0","1","0","1","0","0","0","1"},
{"1","1","1","1","1","0","1","0","0","0","1"},
{"1","0","1","M","1","0","1","0","0","0","1"},
{"1","0","0","0","0","0","1","0","0","0","1"},
{"1","1","1","1","1","1","1","1","1","1","1"},
};
Maze m = new Maze(size, board);
m.findPath();
}
}
这里是电流输出：
The board number 1 is:
11111111111
1PPPPP1PPP1
1P1PPP1P1P1
EP1PPPPP1P1
101111101P1
10101PPP1P1
10001P1PPP1
11111P1PP01
101M1P1PP01
100PPP1PP01
11111111111
The board number 2 is:
11111111111
1PPPPP1PPP1
1P1PPP1P1P1
EP100PPP1P1
101111101P1
10101PPP1P1
10001P1PPP1
11111P1PP01
101M1P1PP01
100PPP1PP01
11111111111
The board number 348 is:
11111111111
1PPPPP10001
1P1PPP10101
EP1PPPPP101
1011111P101
10101PPP101
10001P10001
11111P10001
101M1P10001
100PPP10001
11111111111
编辑：我添加如果（板[X ] [y] .equals（“P”））board [x] [y] =“1”;在findIndex开始。我也修复了x < = 0的问题。我更新了输出到我现在得到的（它实际上是打印348个类似的板）。
当你说它需要找到“所有可能的路径”时，这是否意味着迷宫将包含循环？在循环存在的情况下对“所有可能的路径”进行严格的解释可能需要无数的路径 - 你是指所有不访问节点两次的路径？ – bdonlan
正确 - 它会访问一个节点两次。 –
在leftAvailability中，您仍然使用y-1而不是x-1。 – CoderTao