0
미로에 대한 최단 경로 알고리즘을 성공적으로 완료했습니다 (아래 코드 참조). 그러나, 내 함수에 전달되는 스택 매개 변수에 최단 경로 좌표를 저장하고 싶습니다. 누군가가 이걸 어떻게 달성 할 수 있는지 조언 해 주시겠습니까?최단 경로에 대한 모든 셀 좌표를 인쇄합니다.
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" },
};
내 알고리즘 말 :
전설 : 1 : 벽, 0 : 유효한 경로, S : 시작, 전자 는 여기에 내가 작업하고있는 미로
// 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;
}
}
}
}