我正在尝试编写一个给迷宫的程序,并试图找到出路 . 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
编辑:我添加了if(board [x] [y] .equals(“P”))board [x] [y] =“1”;在findIndex的开头 . 我还修复了x <= 0的问题 . 我将输出更新为我现在得到的(实际上是打印348个类似的板) .
2 回答
我在线上放了一个部分猜猜:
x-1应为y-1
你会发现的另一个问题是,你正在使用其他if块 . 如果遇到分支,请说
你会试着先行,然后当它失败时,它不会试图上升 . 你可以在测试输出中看到
以十六进制编号,方便阅读 . 它进入右下角,然后卡住;没有其他地方可以去打印板,并且递归结束时没有回溯到未经测试的方块 .
再次编辑 . 仍在寻找,但在左/右可用性中你有另一个x / y不匹配,你可能只想在x-1 <0(或y-1)时拒绝可用性;目标节点位于y = 0 .
有了这些更改,并且仅在x == eX && y == eY时才有触发器,我正在获得解决方案的输出 . 很多解决方案,但解决方案 .
编辑计数的另一个幽默事实:你有向左/向右和向上/向下向后 . x坐标指定您正在查看的输入行,y坐标指定列 . 在这种情况下使用r / c是相当普遍的 .
标准路径查找算法应该有效,您需要修改它们以匹配您的世界定义 .
但A *或D *算法效果很好 . 他们使用图表,您应该可以从世界定义中定义图表 . (http://en.wikipedia.org/wiki/A *)
Dijstra的算法也应该用于寻找路径(再次使用图表) . 它通常用于网络路由 - 但它也适用于正常的路径查找 . (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
基本上我的方法是将你的迷宫定义变成一个图形(节点是“连接点”,边缘是“走廊”),然后使用其中一种算法 .