POJ 1383 - Labyrinth

http://poj.org/problem?id=1383

概要

R * C のグリッドが与えられ，岩のあるマスとロープを結び付ける鉤のあるマスとがある． 任意の2点間を結ぶのに必要な最短のロープの長さを答える．

制約

解法

3つ目の制約から木であることがわかる．

木のノードの最長パスは，まず適当な点をルートとして BFS で最も遠いノードを調べ， そのノードをルートとして再び最も遠いノードを調べることで求められる．

 1 #include <cstdio>
 2 #include <queue>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int R, C;
 7 char grid[1000][1001];
 8 static const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
 9 
10 int bfs(pair<int,int>& start)
11 {
12   static int dist[1000][1000];
13   for (int i = 0; i < R; i++) {
14     fill_n(dist[i], C, 10000000);
15   }
16   queue<pair<int,int> > q;
17   q.push(start);
18   dist[start.first][start.second] = 0;
19   int ans = 0;
20   while (!q.empty()) {
21     const int i = q.front().first;
22     const int j = q.front().second;
23     q.pop();
24     if (dist[i][j] > ans) {
25       ans = dist[i][j];
26       start = make_pair(i, j);
27     }
28     for (int d = 0;d < 4; d++) {
29       const int k = i + di[d], l = j + dj[d];
30       if (grid[k][l] == '.' && dist[i][j]+1 < dist[k][l]) {
31         dist[k][l] = dist[i][j]+1;
32         q.push(make_pair(k, l));
33       }
34     }
35   }
36   return ans;
37 }
38 
39 int main()
40 {
41   int T;
42   scanf("%d", &T);
43   while (T-- > 0) {
44     scanf("%d %d", &C, &R);
45     pair<int,int> start(-1, -1);
46     for (int i = 0; i < R; i++) {
47       scanf("%s", grid[i]);
48       for (int j = 0; start.first == -1 && j < C; j++) {
49         if (grid[i][j] == '.') {
50           start = make_pair(i, j);
51         }
52       }
53     }
54 
55     bfs(start);
56     printf("Maximum rope length is %d.\n", bfs(start));
57   }
58   return 0;
59 }
poj/1383.cc