java - 找到有障碍物的两点之间的最短路径

Question

我需要在给定障碍物的情况下找到网格中两点之间的最短路径。

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.

我想出了下面的代码，但我想从面试的角度了解解决这个问题的最有效算法是什么？有没有更好的方法来做到这一点？

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

Answer 1

解决这类问题最有效的算法是BFS (Breadth-first search)如果从一点到另一点的成本是固定的。如果成本可变但为正，那么您需要使用 Dijkstra Algorithm如果有可能出现负成本，Bellman-Ford algorithm将是正确的选择。

还有一点，要让自己对这类问题感到舒服，一种方法就是多解决这类问题。您会在 this 中找到此类问题网站。