0
我已成功完成迷宮的最短路徑算法（請參閱下面的代碼）。但是，我想將最短路徑的座標存儲到傳遞給我的函數的Stack參數中。有人能告訴我如何實現這一目標嗎？ 下面是我對工作的迷宮：打印出最短路徑的所有單元格座標
注：1：長城，0：有效路徑，S：開始E：結束
String[][] map = new String[][]
{
new String[] { "1","1","1","0","0","0","1","1","1","1" },
new String[] { "s","0","0","0","1","1","0","0","0","1" },
new String[] { "1","1","0","0","1","0","0","1","0","1" },
new String[] { "1","1","1","0","0","0","0","0","0","1" },
new String[] { "1","0","1","1","1","0","1","1","0","1" },
new String[] { "0","0","0","0","0","0","0","0","0","1" },
new String[] { "0","1","1","1","1","1","1","1","1","1" },
new String[] { "0","0","0","0","0","0","0","0","0","e" },
};
我的算法：
// Pre-condition: Two integers indicating the row and col number to start from,
// a 2d array of string objects representing the map of the maze,
// a 2d array of booleans mapping out the visited cells in the maze
// A string array containing the map of the maze.
// An empty Stack object
// Post-conditon: The distance of the shortest path from the current cell(start)
// to the end of the maze
public static int shortestPath(int row,int col,boolean[][] visited,String[][] map,Stack<Pair> path)
{
if(row < 0 || row >= map.length || col < 0 || col >= map[0].length)
return -1;
else if(visited[row][col] == true)
return -1;
else if(map[row][col].equals("e"))
return 0;
else
{
// Mark the current cell as visited
visited[row][col] = true;
// There is a wall
if(map[row][col].equals("1"))
return -1;
else
{
int[] pathDist = new int[4];
// Start finding the path from the left
int left = 1 + shortestPath(row,col-1,visited,map,path);
// Start searching from the right
int right = 1 + shortestPath(row,col+1,visited,map,path);
// Start searching from the bottom
int down = 1 + shortestPath(row+1,col,visited,map,path);
// Start searching from the top
int up = 1 + shortestPath(row-1,col,visited,map,path);
visited[row][col] = false;
pathDist[0] = left;
pathDist[1] = right;
pathDist[2] = down;
pathDist[3] = up;
Arrays.sort(pathDist);
for(Integer i : pathDist)
if(i > 0) return i;
return -1;
}
}
}
}