Below is the code which finds out the shortest path, and am trying to print only the shortest Path but am getting all possible Paths that were visited, I was able to do it in Python, but am having hard time doing it in Java and am wondering if there is a better way to do it in Java.
Python Solution
def helper(grid):
m,n=len(grid),len(grid[0])
deque=collections.deque([[(0,0)]])
seen=set()
while deque:
arr=deque.popleft()
i,j=arr[-1]
if (i,j)==(m-1,n-1):
return arr
seen.add((i,j))
possible=[(x,y) for x,y in [(i 1,j),(i-1,j),(i,j 1),(i,j-1)] if 0<=x<m and 0<=y<n and grid[x][y]!=1]
for x,y in possible:
if (x,y) not in seen:
deque.append(arr [(x,y)])
grid=[
[0,0,0,0,0,0,0],
[0,0,1,0,0,1,0],
[0,0,1,0,1,1,0],
[0,0,1,0,1,0,1],
[1,1,1,0,0,0,0]
]
print(helper(grid))
Python code prints the expected output as (0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (1, 3) -> (2, 3) -> (3, 3) -> (4, 3) -> (4, 4) -> (4, 5) -> (4, 6)
Java
import java.util.*;
class Main {
private static int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public static void main(String[] args) {
int[][] grid = {
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 1, 0},
{0, 0, 1, 0, 1, 1, 0},
{0, 0, 1, 0, 1, 0, 1},
{1, 1, 1, 0, 0, 0, 0}
};
int[][] path = shortestPath(grid);
System.out.println("shortestPath " Arrays.deepToString(path));
}
public static int[][] shortestPath(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
if (grid == null || grid.length == 0 || grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return new int[][]{{-1, -1}};
int[][] path = bfs_with_visited(grid, m, n);
return path;
}
private static int[][] bfs_with_visited(int[][] grid, int m, int n) {
boolean[][] visited = new boolean[m][n];
visited[0][0] = true;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0});
List<int[]> result = new ArrayList<>();
int path = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i ) {
int[] currentCell = queue.remove();
result.add(new int[]{currentCell[0], currentCell[1]});
if (currentCell[0] == m - 1 && currentCell[1] == n - 1) {
return result.toArray(new int[result.size()][2]);
}
visitNeighbours(grid, m, n, visited, queue, currentCell);
}
path ;
}
return new int[][]{{-1, -1}};
}
private static void visitNeighbours(int[][] grid, int m, int n, boolean[][] visited, Queue<int[]> queue, int[] currentCell) {
for (int k = 0; k < dir.length; k ) {
int nextX = dir[k][0] currentCell[0];
int nextY = dir[k][1] currentCell[1];
if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextX][nextY] && grid[nextX][nextY] == 0) {
queue.add(new int[]{nextX, nextY});
visited[nextX][nextY] = true;
}
}
}
}
Appreciate your inputs, TIA.
CodePudding user response：
In your python program if you put a print statement after arr = deque.popleft() you will see the following:
[(0, 0)]
[(0, 0), (1, 0)]
[(0, 0), (0, 1)]
[(0, 0), (1, 0), (2, 0)]
[(0, 0), (1, 0), (1, 1)]
[(0, 0), (0, 1), (1, 1)]
[(0, 0), (0, 1), (0, 2)]
[(0, 0), (1, 0), (2, 0), (3, 0)]
[(0, 0), (1, 0), (2, 0), (2, 1)]
[(0, 0), (1, 0), (1, 1), (2, 1)]
[(0, 0), (0, 1), (1, 1), (2, 1)]
[(0, 0), (0, 1), (0, 2), (0, 3)]
[(0, 0), (1, 0), (2, 0), (3, 0), (3, 1)]
[(0, 0), (1, 0), (2, 0), (2, 1), (3, 1)]
[(0, 0), (1, 0), (1, 1), (2, 1), (3, 1)]
[(0, 0), (0, 1), (1, 1), (2, 1), (3, 1)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (1, 4)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 6)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (4, 4)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 6), (2, 6)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (4, 4), (4, 5)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (4, 4), (4, 5), (3, 5)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (4, 4), (4, 5), (4, 6)]
If you can see, the python program is appending a list to the queue not just one coordinate which means it remembers the path that it traversed or in other words it carries the path all along.
If you want to emulate the same thing in Java, you can do it as below:
private static int[][] bfs_with_visited(int[][] grid, int m, int n) {
boolean[][] visited = new boolean[m][n];
visited[0][0] = true;
Deque<List<int[]>> queue = new ArrayDeque<>();
List<int[]> result = new ArrayList<>();
result.add(new int[] {0,0});
queue.addFirst(result);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i <size; i ) {
result = queue.removeFirst();
int[] curr = result.get(result.size()-1);
if (curr[0] == m-1 && curr[1] == n-1) {
return result.toArray(new int[result.size()][2]);
}
visited[curr[0]][curr[1]] = true;
visitNeighbours(grid, m, n, visited, queue, result, curr);
}
}
return new int[][]{{-1, -1}};
}
private static void visitNeighbours(int[][] grid, int m, int n, boolean[][] visited, Deque<List<int[]>> queue,
List<int[]> listSoFar, int[] currentCell) {
for (int k = 0; k < dir.length; k ) {
int nextX = dir[k][0] currentCell[0];
int nextY = dir[k][1] currentCell[1];
if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextX][nextY] && grid[nextX][nextY] == 0) {
List<int[]> l = new ArrayList<>(listSoFar);
l.add(new int[] {nextX, nextY});
queue.add(l);
}
}
}
But I won't suggest this. Instead create a class like
class Node {
int[] prev = null;
int[] curr = null;
public Node(int[] curr, int[] prev) {
this.curr = curr;
this.prev = prev;
}
}
and use this to populate your queue. When you find the target Node track the path by using the prev field until you reach a null prev.