POJ 1387 Labyrinth

問題

やりかた

木の直径を求める問題。グラフ上の適当な点からはじめて最も遠い点を見つける。続いてその点から最も遠い点を探すとその間が直径になる。
メモリ量、制限時間ともにシビア。グラフは隣接リストで持たずに、ある頂点に対する４方向の連結情報をビット状態で持つようにして、一つの頂点の情報をcharで表現してメモリを減らした。

以下ソース。

int R, C;
char f[1001][1001];
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};

char G[1000001];
int d[1000001];

void bfs(int idx){
  memset(d, -1, sizeof(d));

  queue<int> Q;
  Q.push(idx);
  d[idx] = 0;
  while(!Q.empty()){
    int x = Q.front(); Q.pop();
    for(int k = 0; k < 4; k++){
      if(G[x] >> k & 1){
	int v = x + dy[k] * C + dx[k];
	if(d[v] == -1){
	  Q.push(v);
	  d[v] = d[x] + 1;
	}
      }
    }
  }

  return;
}

int main(){
  int T;
  scanf("%d", &T);
  while(T--){
    scanf("%d %d", &C, &R);
    for(int i = 0; i < R; i++){
      for(int j = 0; j < C; j++){
	f[i][j] = getchar();
      }
      getchar();
    }
    memset(G, 0, sizeof(G));
    
    int start;
    for(int i = 0; i < R; i++){
      for(int j = 0; j < C; j++){
	if(f[i][j] == '.'){
	  start = i * C + j;
	  for(int k = 0; k < 4; k++){
	    int ny = i + dy[k], nx = j + dx[k];
	    if(0 <= ny && ny < R
	       && 0 <= nx && nx < C && f[ny][nx] == '.'){
	      G[i * C + j] |= 1 << k;
	    }
	  }
	}
      }
    }

    //木の直径
    bfs(start);
    int fur = max_element(d, d + R * C) - d;
    bfs(fur);
    int ans = *max_element(d, d + R * C);
    printf("Maximum rope length is %d.\n", ans);
  }
  return 0;
}