//题目是假想你手里有一份博物馆地图（square matrix of char），G代表guard #代表locked room，. 代表empty room。
//计算每一个空房间，最近的guard 到他需要多久（移动一格消耗一个单位时间，只能横向竖向移动，locked room是打不开的）。try to do it in one pass


public static int[][] DistToGuard(char[][] matrix) {
  Queue<Pair> queue = new Queue<Pair>();
  int m = matrix.length;
  int n = matrix[0].length;
  int[][] dist = new int[m][n];
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (matrix[i][j] == 'G') {
        queue.offer( new Pair(i, j) );
        dist[i][j] = 0;
      } else {
        dist[i][j] = Integer.MAX_VALUE;
      }
    }
  }

  while (!queue.isEmpty()) {
    Pair p = queue.poll();
    int i = p.left;
    int j = p.right;
    if (i + 1 < m && matrxi[i + 1, j] == '.' && dist[i+1][j] > dist[i][j] + 1) {
      dist[i+1][j] = dist[i][j] + 1;
      queue.offer(new Pair(i + 1, j))
    }
    if (j + 1 < m && matrxi[i, j + 1] == '.' && dist[i][j+1] > dist[i][j] + 1) {
      dist[i][j+1] = dist[i][j] + 1;
      queue.offer(new Pair(i, j + 1))
    }
    if (i - 1 >= 0 && matrxi[i - 1, j] == '.' && dist[i-1][j] > dist[i][j] + 1) {
      dist[i-1][j] = dist[i][j] + 1;
      queue.offer(new Pair(i - 1, j))
    }
    if (j - 1 >= 0 && matrxi[i, j - 1] == '.' && dist[i][j-1] > dist[i][j] + 1) {
      dist[i][j-1] = dist[i][j] + 1;
      queue.offer(new Pair(i, j - 1))
    }
  }

  return dist;

}

private static class Pair {
    int left;
    int right;
}