Given a gym with k pieces of equipment and some obstacles. We bought a chair and wanted to put this chair into the gym such that the sum of theshortest path costfrom the chair to the k pieces of equipment is minimal. The gym is represented by a char matrix, ‘E’ denotes a cell with equipment, ‘O’ denotes a cell with an obstacle, 'C' denotes a cell without any equipment or obstacle. You can only move to neighboring cells (left, right, up, down) if the neighboring cell is not an obstacle. The cost of moving from one cell to its neighbor is 1. You can not put the chair on a cell with equipment or obstacle.

Assumptions

• There is at least one equipment in the gym
• The given gym is represented by a char matrix of size M * N, where M > = 1 and N > = 1, it is guaranteed to be not null
• It is guaranteed that each 'C' cell is reachable from all 'E' cells.
• If there does not exist such place to put the chair, just return null (Java) empty vector (C++)

Examples

{ { 'E', 'O', 'C' },

{ 'C', 'E', 'C' },

{ 'C', 'C', 'C' } }

we should put the chair at (1, 0), so that the sum of cost from the chair to the two equipment is 1 + 1 = 2, which is minimal.

Solution: 反向BFS，以房子为起点，统计房子到各个空位的距离。注意obstacle不能放入queue （要区分房子能不能通过，如果不能通过，房子也不能放入queue）。另外要用reach_equip[][]统计各空位可以到达房子的个数。统一在加入queue时更新distance[][], reach[][], visited[][]

  public List<Integer> putChair(char[][] gym) {
    int m = gym.length, n = gym[0].length, count = 0;
    int[][] distance = new int[m][n];
    int[][] reach_equip = new int[m][n];
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    Queue<Node> queue = new LinkedList<>();
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (gym[i][j] == 'E') {
          count++;
          boolean[][] visited = new boolean[m][n];
          queue.offer(new Node(i, j));
          visited[i][j] = true;
          int level = 1;
          while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
              Node cur = queue.poll();
              for (int l = 0; l < 4; l++) {
                int x = cur.x + dx[l];
                int y = cur.y + dy[l];
                if (x >= 0 && x < m && y >= 0 && y < n && gym[x][y] != 'O' && !visited[x][y]) {
                  queue.offer(new Node(x, y));
                  //统一在加入queue时更新状态
                  visited[x][y] = true;
                  distance[x][y] += level;
                  reach_equip[x][y]++;
                }
              }
            }
            level++;
          }
        }
      }
    }
    int index1 = -1, index2 = -1, min = Integer.MAX_VALUE;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (gym[i][j] == 'C' && reach_equip[i][j] == count && distance[i][j] < min) {
          index1 = i;
          index2 = j;
          min = distance[i][j];
        }
      }
    }
    if (index1 != -1) {
      List<Integer> ans = new ArrayList<>();
      ans.add(index1);
      ans.add(index2);
      return ans;
    } 
    return null;
  }

Solution 2: 若没有obstacle，则是manhatan distance, 答案坐标=（所有E的x坐标的中位数，所有E的y坐标的中位数）.（线段上中点到其他点的距离和最小）