AOJ 2302 - On or Off

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2302

概要

R x C の部屋と壁からなるマップが与えられる． M 個の (r[i], c[i]) にある部屋を与えられた順に巡る． スタート地点は (r[0], c[0])，ゴール地点は (r[M-1], c[M-1])．

部屋に入るときは必ずその部屋の電気をつけなければならない． ゴール地点についたときには全ての部屋の電気が消えていなければならない．

各部屋の電気には

が設定されている．

コストが最小になるように電気を操作したとき，そのときのコストを出力する．

制約

解法

通る部屋の時刻は一意に決まるので，シミュレーションにより通る時刻を記録し，2回以上通る部屋について，つけっぱなしの方が良いか，消してから付ける方が良いかを計算する． 

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 int counter = 0;
 7 
 8 void bfs(vector<vector<vector<int> > >& stamps, const vector<string>& grid, const pair<int,int>& start, const pair<int,int>& goal)
 9 {
10   const int R = grid.size(), C = grid[0].size();
11   queue<pair<int,int> > q;
12   q.push(start);
13   vector<vector<int> > prev(R, vector<int>(C, -1));
14   while (!q.empty()) {
15     if (q.front() == goal) {
16       break;
17     }
18     const int i = q.front().first;
19     const int j = q.front().second;
20     q.pop();
21 
22     for (int d = 0; d < 4; d++) {
23       static const int di[] = {1, -1, 0, 0};
24       static const int dj[] = {0, 0, 1, -1};
25       const int k = i + di[d], l = j + dj[d];
26       if (0 <= k && k < R && 0 <= l && l < C && grid[k][l] == '.' && prev[k][l] == -1) {
27         prev[k][l] = i*C + j;
28         q.push(make_pair(k, l));
29       }
30     }
31   }
32   vector<pair<int,int> > path;
33   for (pair<int,int> pos = goal; pos != start;) {
34     path.push_back(pos);
35     const int p = prev[pos.first][pos.second];
36     pos.first = p/C;
37     pos.second = p%C;
38   }
39   for (vector<pair<int,int> >::reverse_iterator it = path.rbegin(); it != path.rend(); ++it) {
40     stamps[it->first][it->second].push_back(counter++);
41   }
42 }
43 
44 int main()
45 {
46   int R, C, M;
47   cin >> R >> C >> M;
48   vector<string> grid(R);
49   for (int i = 0; i < R; i++) {
50     cin >> grid[i];
51   }
52   static int keep_costs[50][50], on_costs[50][50], off_costs[50][50];
53   for (int i = 0; i < R; i++) {
54     for (int j = 0; j < C; j++) {
55       cin >> keep_costs[i][j];
56     }
57   }
58   for (int i = 0; i < R; i++) {
59     for (int j = 0; j < C; j++) {
60       cin >> on_costs[i][j];
61     }
62   }
63   for (int i = 0; i < R; i++) {
64     for (int j = 0; j < C; j++) {
65       cin >> off_costs[i][j];
66     }
67   }
68   static pair<int,int> rooms[1000];
69   for (int i = 0; i < M; i++) {
70     cin >> rooms[i].first >> rooms[i].second;
71   }
72 
73   vector<vector<vector<int> > > stamps(R, vector<vector<int> >(C));
74   stamps[rooms[0].first][rooms[0].second].push_back(counter++);
75   for (int i = 0; i < M-1; i++) {
76     bfs(stamps, grid, rooms[i], rooms[i+1]);
77   }
78   int ans = 0;
79   for (int i = 0; i < R; i++) {
80     for (int j = 0; j < C; j++) {
81       const vector<int>& s = stamps[i][j];
82       if (!s.empty()) {
83         const int keep = keep_costs[i][j];
84         const int on = on_costs[i][j];
85         const int off = off_costs[i][j];
86         ans += on;
87         for (vector<int>::const_iterator it = s.begin(); it+1 != s.end(); ++it) {
88           ans += min(off + on, keep*(*(it+1) - *it));
89         }
90         ans += off;
91       }
92     }
93   }
94   cout << ans << endl;
95   return 0;
96 }
aoj/2302.cc