在后面的二维数组中,#代表迷宫的墙壁,点代表迷宫中可能路径中的正方形。只能移动到数组中包含点的位置...我需要一个递归方法mazeTraverse来"行走"迷宫。它应该接收数组和迷宫的起始位置作为参数。当它试图找到迷宫的出口时,它应该在路径中的每个方块中放置字符"X"。该方法应在每次移动后显示迷宫,以便用户可以观看迷宫的解决。
我真的不确定如何超越这一点。感谢任何可以提供帮助的人。
public class BonusMaze {
public static void main(String args[]){
char field[][]={
{'#','#','#','#','#','#','#','#','#','#','#','#'},
{'#','•','•','•','#','•','•','•','•','•','•','#',},
{'•','•','#','•','#','•','#','#','#','#','•','#',},
{'#','#','#','•','#','•','•','•','•','#','•','#',},
{'#','•','•','•','•','#','#','#','•','#','•','•',},
{'#','#','#','#','•','#','•','#','•','#','•','#',},
{'#','•','•','#','•','#','•','#','•','#','•','#',},
{'#','#','•','#','•','#','•','#','•','#','•','#',},
{'#','•','•','•','•','•','•','•','•','#','•','#',},
{'#','#','#','#','#','#','•','#','#','#','•','#',},
{'#','•','•','•','•','•','•','#','•','•','•','#',},
{'#','#','#','#','#','#','#','#','#','#','#','#'},
};
printField(field);
mazeTraverse(field,2,0);
}
public static void mazeTraverse(char[][] field, int x, int y){
field[2][0]='X';
if(field[x+1][y]=='•'){
field[x+1][y]='X';
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x-1][y]=='•'){
field[x-1][y]='X';
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y+1]=='•'){
field[x][y+1]='X';
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y-1]=='•'){
field[x][y-1]='X';
printField(field);
mazeTraverse(field,x+1,y);
}
}
public static void printField(char[][] field){
for(int x=0; x<11; x++){
for(int y=0; y<11; y++){
System.out.print(field[x][y]);
}
System.out.println();
}
System.out.print("nn");
}
}
我把它改成这个,但它都很古怪:
public class BonusMaze {
public static boolean east=true, north=false, south=false, west=false;
/*
east=false;
north=false;
south=false;
west=false;
*/
public static void main(String args[]){
char field[][]={
{'#','#','#','#','#','#','#','#','#','#','#','#'},
{'#','•','•','•','#','•','•','•','•','•','•','#',},
{'•','•','#','•','#','•','#','#','#','#','•','#',},
{'#','#','#','•','#','•','•','•','•','#','•','#',},
{'#','•','•','•','•','#','#','#','•','#','•','•',},
{'#','#','#','#','•','#','•','#','•','#','•','#',},
{'#','•','•','#','•','#','•','#','•','#','•','#',},
{'#','#','•','#','•','#','•','#','•','#','•','#',},
{'#','•','•','•','•','•','•','•','•','#','•','#',},
{'#','#','#','#','#','#','•','#','#','#','•','#',},
{'#','•','•','•','•','•','•','#','•','•','•','#',},
{'#','#','#','#','#','#','#','#','#','#','#','#'},
};
printField(field);
field[2][0]='X';
mazeTraverse(field,2,0);
}
public static void mazeTraverse(char[][] field, int x, int y){
if(x==2&&y==0){
field[2][1]='X';
mazeTraverse(field,2,1);
printField(field);
}
if(east){
if(field[x][y+1]=='•' || field[x+1][y]=='X'){
field[x][y+1]='X';
}
if(field[x+1][y+1]=='•'){
east=false;
north=false;
south=false;
west=false;
south=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y+2]=='•'){
east=false;
north=false;
south=false;
west=false;
east=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x-1][y+1]=='•'){
east=false;
north=false;
south=false;
west=false;
north=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y+1]=='#'){
east=false;
north=false;
south=false;
west=false;
west=true;
printField(field);
mazeTraverse(field,x-1,y);
}
}
else if(west){
if(field[x-1][y]=='•' || field[x-1][y]=='X'){
field[x-1][y]='X';
}
if(field[x+1][y+1]=='•'){
east=false;
north=false;
south=false;
west=false;
south=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y+2]=='•'){
east=false;
north=false;
south=false;
west=false;
east=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x-1][y+1]=='•'){
east=false;
north=false;
south=false;
west=false;
north=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y+1]=='#'){
east=false;
north=false;
south=false;
west=false;
west=true;
printField(field);
mazeTraverse(field,x-1,y);
}
}
else if(north){
if(field[x][y+1]=='•' || field[x][y+1]=='X'){
field[x][y+1]='X';
}
if(field[x+1][y+1]=='•'){
east=false;
north=false;
south=false;
west=false;
south=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y+2]=='•'){
east=false;
north=false;
south=false;
west=false;
east=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x-1][y+1]=='•'){
east=false;
north=false;
south=false;
west=false;
north=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y+1]=='#'){
east=false;
north=false;
south=false;
west=false;
west=true;
printField(field);
mazeTraverse(field,x-1,y);
}
}
else if(south){
if(field[x][y-1]=='•' || field[x][y-1]=='X'){
field[x][y-1]='X';
}
if(field[x+1][y+1]=='•'){
east=false;
north=false;
south=false;
west=false;
south=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y+2]=='•'){
east=false;
north=false;
south=false;
west=false;
east=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x-1][y+1]=='•'){
east=false;
north=false;
south=false;
west=false;
north=true;
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y+1]=='#'){
east=false;
north=false;
south=false;
west=false;
west=true;
printField(field);
mazeTraverse(field,x-1,y);
}
}
/*if(field[x+1][y]=='•'){
field[x+1][y]='X';
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x-1][y]=='•'){
field[x-1][y]='X';
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y+1]=='•'){
field[x][y+1]='X';
printField(field);
mazeTraverse(field,x+1,y);
}
else if(field[x][y-1]=='•'){
field[x][y-1]='X';
printField(field);
mazeTraverse(field,x+1,y);
}*/
}
public static void printField(char[][] field){
for(int x=0; x<12; x++){
for(int y=0; y<12; y++){
System.out.print(field[x][y]);
}
System.out.println();
}
System.out.print("nn");
}
}
由于需要递归,因此可能需要DFS(深度优先搜索)。来自维基百科
procedure DFS(G,v):
2 label v as discovered
3 for all edges e in G.adjacentEdges(v) do
4 if edge e is unexplored then
5 w ← G.adjacentVertex(v,e)
6 if vertex w is unexplored then
7 label e as a discovered edge
8 recursively call DFS(G,w)
9 else
10 label e as a back edge
11 label v as explored
程序的边缘是你现在正在检查的单元格的四个(最多)邻居。如果找到出口,则标记单元格,然后返回。这是一般的想法。您现在可以自己找到详细信息。
求救(注意桌子的边框)我希望我有所帮助
我使用了以下算法。如果还没有在出口处,它会尝试向右走,然后尝试向前走,然后尝试向左走。 如果其中任何一个返回到末尾的路径,则返回该路径。 如果它们返回 null,则尝试下一个方向。
通过总是试图先向右走,它模拟了坚持右墙的策略
traverse(Position p, Direction d, String pathSoFar)
if atEndPosition(p)
return pathSoFar + p;
if canTravelRight(p, d)
result = traverse(poitionToRight, directionToRight, pathSoFar + p)
if result return result
if canTravelForward(p, d)
result = traverse(positionForward, d, pathSoFar + p)
if result return result
if canTravelLeft(p, d)
result = traverse(positionToLeft, directionToLeft, pathSoFar + p)
return result
我使用了一个非常简单的逻辑来找到右边的下一个方向,如果电流是北,那么下一个是东,依此类推。 如果向东移动,则移动的逻辑同样简单,新的x位置是旧的x + 1,新的y位置是旧的y位置。 在计算位置时,我没有进行任何边界检查,而只是尝试查看新位置是否在路径上。 如果新位置是一堵墙,或者如果 ArrayIndexOutOfBoundsException,则 canTravelxxx 返回 false