Доброго времени суток!
Использую алгоритм поиска в ширину для определения кратчайшего пути в двумерном массиве. Работает корректно,
однако не могу получить путь, пройденный от источника к месту назначения в виде очереди или списка.
public class SearchMazeBFS {
private static final int ROW = 9;
private static final int COL = 10;
private int[] rowNum = new int[] { -1, 0, 0, 1 };
private int[] colNum = new int[] { 0, -1, 1, 0 };
private static class Point {
private Point(int row, int col) {
this.x = row;
this.y = col;
}
private int x;
private int y;
}
private static class QueueNode {
private QueueNode(Point src, int d) {
this.pt = src;
this.dist = d;
}
private Point pt;
private int dist;
}
private boolean isValid(int row, int col) {
return (((row >= 0) && (row < ROW)) && ((col >= 0) && (col < COL)));
}
private int BFS(int mat[][], Point src, Point dest) {
if ((mat[src.x][src.y] == 0) || (mat[dest.x][dest.y] == 0))
return Integer.MAX_VALUE;
boolean[][] visited = new boolean[ROW][COL];
visited[src.x][src.y] = true;
Queue<QueueNode> q = new ArrayDeque<>();
QueueNode s = new QueueNode(src, 0);
q.add(s);
while (!q.isEmpty()) {
QueueNode curr = q.peek();
Point pt = curr.pt;
if (pt.x == dest.x && pt.y == dest.y) {
return curr.dist;
}
q.poll();
for (int i = 0; i < 4; i++) {
int row = pt.x + rowNum[i];
int col = pt.y + colNum[i];
if ((isValid(row, col) && mat[row][col] == 1)
&& !visited[row][col]) {
visited[row][col] = true;
QueueNode adjCell = new QueueNode(new Point(row, col),
curr.dist + 1);
q.add(adjCell);
}
}
}
return Integer.MAX_VALUE;
}
public static void main(String[] args) {
SearchMazeBFS smbfs = new SearchMazeBFS();
int[][] mat = new int[][] {
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }
};
Point source = new SearchMazeBFS.Point(0, 2);
Point dest = new SearchMazeBFS.Point(2, 0);
int dist = smbfs.BFS(mat, source, dest);
if (dist != Integer.MAX_VALUE)
System.out.println("Shortest Path is " + dist);
else
System.out.println("Shortest Path doesn't exist");
}
}
Простой
