POJ 1101 - The Game

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

概要

w * h のグリッド上にいくつか正方形が置かれている．

(x1, y1) にある正方形から (x2, y2) にある正方形まで，何本かの真っ直ぐな線分で繋ぎたい． ただし，その線分は

• 水平方向か垂直方向である
• 他の正方形と交わってはいけない

という条件を満たす． 線分は w * h のグリッドの外側に引いてもよい．

最低何本の線分で繋げるかを答える．

制約

• 1 <= w, h <= 75

解法

BFS するだけ． 外側に線分を引く場合，最短経路では1マス分しか外側を使わない．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 int bfs(const vector<string>& grid, int x1, int y1, int x2, int y2)
 7 {
 8   const int H = grid.size();
 9   const int W = grid[0].size();
10   vector<vector<int> > dist(H, vector<int>(W, 1000000));
11   queue<pair<int,int> > q;
12   q.push(make_pair(y1, x1));
13   dist[y1][x1] = 0;
14   while (!q.empty()) {
15     const int i = q.front().first;
16     const int j = q.front().second;
17     q.pop();
18     for (int d = 0; d < 4; d++) {
19       for (int s = 1;; s++) {
20         static const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
21         const int k = i + s*di[d];
22         const int l = j + s*dj[d];
23         if (0 <= k && k < H && 0 <= l && l < W) {
24           if (k == y2 && l == x2) {
25             return dist[i][j]+1;
26           }
27           if (grid[k][l] == ' ' && dist[k][l] > dist[i][j]+1) {
28             dist[k][l] = dist[i][j]+1;
29             q.push(make_pair(k, l));
30           } else {
31             break;
32           }
33         } else {
34           break;
35         }
36       }
37     }
38   }
39   return -1;
40 }
41 
42 int main()
43 {
44   int T = 0;
45   int W, H;
46   while (cin >> W >> H && W != 0) {
47     vector<string> grid(H+2);
48     grid[0] = grid[H+1] = string(W+2, ' ');
49     cin.ignore();
50     for (int i = 1; i <= H; i++) {
51       getline(cin, grid[i]);
52       grid[i] = string(" ") + grid[i] + " ";
53     }
54 
55     int x1, y1, x2, y2;
56     cout << "Board #" << ++T << ":" << endl;
57     int c = 0;
58     while (cin >> x1 >> y1 >> x2 >> y2 && x1 != 0) {
59       const int r = bfs(grid, x1, y1, x2, y2);
60       cout << "Pair " << ++c << ": ";
61       if (r == -1) {
62         cout << "impossible." << endl;
63       } else {
64         cout << r << " segments." << endl;
65       }
66     }
67     cout << endl;
68   }
69   return 0;
70 }