POJ 1548 - Robots

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

概要

24 * 24 のグリッド上のいくつかのマスにはゴミがある． このゴミをロボットで回収したい．

ロボットは北西のマスからスタートし，東方向か南方向に進みつつゴミを回収し，最終的に南東のマスで終わる．

すべてのゴミを回収するのに必要な最小のロボットの数を答える．

制約

特になし

解法

ゴミが存在する最も北の列のゴミをすべて回収してから南に進む，という貪欲的な戦略が最適なので，これをシミュレーションして何回繰り返す必要があるか調べる．

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int x, y;
 8   while (cin >> x >> y && x != -1) {
 9     static const int N = 24;
10     static bool grid[N][N];
11     for (int i = 0; i < N; i++) {
12       fill_n(grid[i], N, false);
13     }
14     grid[x-1][y-1] = true;
15     int left = 1;
16     while (cin >> x >> y && x != 0) {
17       grid[x-1][y-1] = true;
18       ++left;
19     }
20 
21     int ans = 0;
22     while (left > 0) {
23       ++ans;
24       for (int i = 0, j = 0; i < N;) {
25         bool *p = find(grid[i]+j, grid[i]+N, true);
26         if (p == grid[i]+N) {
27           ++i;
28         } else {
29           j = distance(grid[i], p);
30           *p = false;
31           --left;
32         }
33       }
34     }
35     cout << ans << endl;
36   }
37   return 0;
38 }
poj/1548.cc