# Find the shortest path between two points in a 2D matrix with obstacles

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;
nextToVisit.offer(new int[] {s_row, s_col});
Set<int[]> visited = new HashSet<>();

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;
count++;
}

}

return count;
}

• It would be nice if you could name the algorithm used. If you can not, look at the path finding algorithms that exist. Moreover, I can not find your code very readable. Adding spacing will not cost you anything but improve readability. Commented Nov 20, 2018 at 7:40