POJ 2056 - The Separator in Grid

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

概要

無向グラフ G = (V, E) に対して，G の部分グラフで V \ S が2つの連結成分になるようなものの頂点集合 S を separator と呼ぶ．

この問題では，図のように N * M のグリッド上で W と B を左右に分けるような separator を考える． 単純にするため，この問題における separator は以下の制約を満たすもののみを指す．

  1. minimal である．つまり，S の部分集合で separator となるものは無い
  2. 右上と左上の端を除く一番上の行からスタートし， 同様に右下と左下の端を除く一番下の行で終了する
  3. 上から下へ行くとき，左右には曲がるが上ることはない

separator の初期状態が与えられるので，以下の操作を繰り返した結果の最小の separator の頂点数を答える．

  1. 左に S がある B を S に変える
  2. S を W に変える．ただし，初期状態で B だった S は W に変えることができない．

制約

解法

separator に関する制約から，一番上の行と一番下の行に S は1つしか無いことがわかる (複数あると部分グラフも separator になる)．

また，操作に関する制約から最終的に S になるのは

の2種類しかない．

また，separator の定義から一番右の列や一番左の列に separator のノードがくることはない (もしくると「2つの連結成分」でなくなる)．

このようなノードに関して上から下まで BFS すれば解ける．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int N, M;
 9   while (cin >> N >> M && N != 0) {
10     vector<string> grid(N);
11     for (int i = 0; i < N; i++) {
12       cin >> grid[i];
13     }
14 
15     static const int INF = 10000000;
16     vector<vector<int> > dist(N, vector<int>(M, INF));
17     queue<pair<int,int> > q;
18     for (int j = M-2; j > 0; j--) {
19       if (grid[0][j] == 'S') {
20         dist[0][j] = 1;
21         q.push(make_pair(0, j));
22         break;
23       } else if (grid[0][j-1] == 'S') {
24         dist[0][j] = 1;
25         q.push(make_pair(0, j));
26       }
27     }
28     while (!q.empty()) {
29       const int i = q.front().first;
30       const int j = q.front().second;
31       q.pop();
32       if (i == N-1) {
33         continue;
34       }
35       for (int d = 0; d < 3; d++) {
36         static const int di[] = {0, 0, 1};
37         static const int dj[] = {-1, 1, 0};
38         const int k = i + di[d];
39         const int l = j + dj[d];
40         if (1 <= l && l < M-1
41             && (grid[k][l] == 'S' || grid[k][l-1] == 'S')
42             && dist[i][j]+1 < dist[k][l]) {
43           dist[k][l] = dist[i][j] + 1;
44           q.push(make_pair(k, l));
45         }
46       }
47     }
48     int ans = INF;
49     for (int j = 1; j < M-1; j++) {
50       ans = min(ans, dist[N-1][j]);
51     }
52     cout << ans << endl;
53   }
54   return 0;
55 }
poj/2056.cc