1
\$\begingroup\$

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;
  }
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Calak Nov 20 '18 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.