I need to find shortest path between two points in a grid given an obstacles..
Given a 2 dimensional matrix where some of the elements are filled with 1 and rest of the elements are filled. Here X means you cannot traverse to that particular points. From a cell you can either traverse to left, right, up or down. Given two points in the matrix find the shortest path between these points. Here S is the starting point and E is the Ending point.
I came up with below code which BFS but I wanted to understand from the interview point of view what is the most efficient algorithm to solve this problem? Is there any better way to do this? Can we optimize below code?
public static void main(String[] args) {
char[][] matrix = {{'1','1','1', '1'},
{'1','S','1', '1'},
{'1','1','X', '1'},
{'1','1','1', 'E'}};
System.out.println(shortestPath(matrix));
}
public static int shortestPath(char[][] matrix) {
int s_row = 0, s_col = 0;
boolean flag = false;
for (s_row = 0; s_row < matrix.length; s_row++) {
for (s_col = 0; s_col < matrix[0].length; s_col++) {
if (matrix[s_row][s_col] == 'S')
flag = true;
if (flag)
break;
}
if (flag)
break;
}
return shortestPath(matrix, s_row, s_col);
}
public static int shortestPath(char[][] matrix, int s_row, int s_col) {
int count = 0;
Queue<int[]> nextToVisit = new LinkedList<>();
nextToVisit.offer(new int[] {s_row, s_col});
Set<int[]> visited = new HashSet<>();
Queue<int[]> temp = new LinkedList<>();
while (!nextToVisit.isEmpty()) {
int[] position = nextToVisit.poll();
int row = position[0];
int col = position[1];
if (matrix[row][col] == 'E')
return count;
if (row > 0 && !visited.contains(new int[] {row - 1, col}) && matrix[row - 1][col] != 'X')
temp.offer(new int[] {row - 1, col});
if (row < matrix.length - 1 && !visited.contains(new int[] {row + 1, col})
&& matrix[row + 1][col] != 'X')
temp.offer(new int[] {row + 1, col});
if (col > 0 && !visited.contains(new int[] {row, col - 1}) && matrix[row][col - 1] != 'X')
temp.offer(new int[] {row, col - 1});
if (col < matrix[0].length - 1 && !visited.contains(new int[] {row, col + 1})
&& matrix[row][col + 1] != 'X')
temp.offer(new int[] {row, col + 1});
if (nextToVisit.isEmpty() && !temp.isEmpty()) {
nextToVisit = temp;
temp = new LinkedList<>();
count++;
}
}
return count;
}