第１０回日本情報オリンピック 予選（過去問）E - チーズ (Cheese)
BFS(深さ優先探索)の問題.最短時間で工場見学できるカナ？！
問題の説明
の区画のこの町には
個の工場があり,それぞれの工場が硬さ
のチーズを作っている.チーズの硬さは工場によって異なり,硬さ
から
までのチーズを生産出来る工場がちょうど
つずつある.
最初のネズミの体力はであり,チーズを
個食べる毎に
増える.ただし,自分の体力より硬いチーズを食べる事は出来ない.
ネズミの移動に関するルールは以下の通り.
- ネズミは上下左右,隣り合うマスに
分で移動できる.
- ネズミは工場及び,. のマスを通過する事が出来る.(この時にチーズを食べなくてもよい.)
- X のマスに侵入する事は出来ず,町の外に出る事も出来ない.
- チーズを食べる時間は考えないものとする.
今,ネズミはS からスタートした.上のルールの下で,ネズミが全てのチーズを食べる最短時間を求めよ.
条件
考えた事
問題文がややこしい.おそらく意図的なものではあるが言いたい事が分かりづらくなっている.
何を求めて欲しいか.それはとても簡単である.S→1→2→3→......のように動いていく最短時間を求めればいいのだ.ここで注目したいのは,S→1への行き方と1→2への行き方は全く無関係である事だ.S→1で2分かかったとて,500分かかったとて,1→2の行き方には影響しない.*1
つまり,S,1,2,3......の座標を配列にまとめ,要素[tex:i(0≦i≦N)*2]からに行く場合の最短時間を求める函数をつくり,それを足し合わせれば,ネズミが全てのチーズを食べる最短時間を求められるのだ.
これが例えばチーズを食べた工場が通れなくなるとなると少し面白い.食べた工場を×とする一工夫が必要となる.興味ある方はやってみてもよい.
そのため,main函数では,
for(int i=0;i<H;i++) {
for(int j=0;j<W;j++) {
if(field.at(i).at(j) == 'S') {
fac.at(0).first = i;
fac.at(0).second = j;
}
}
}
とし,Sの座標を事前にまとめておくことには注意が必要である.
続いて,最短経路を求める函数を考えよう.迷路の移動方法については
を見てもらいたい.
BFSでのポイントはqueueである.
queue<P> que;
que.push(P(sx, sy));
dist.at(sx).at(sy) = 0;
while (que.size()) {
P gen = que.front();
que.pop();
としてqueueを作り,その先頭の座標をgenに入れて入手.popして先頭削除を繰り返す.これを行う事で移動時間が短い順に座標を取り出し操作を行える.これと,
que.push(P(nx, ny));
dist.at(nx).at(ny) = dist.at(gen.first).at(gen.second) + 1;
を合わせてdist配列で時間管理する事で,今いるところから+1minで行けるところ全てに記しをつける事が出来る.
図に表すとこんな感じ.まずSから上下左右の範囲で行けるところをqueueに入れ,1(右)1(下)で記しをつけていく.続いて1(右)の座標情報を入手し,そこから行けるところに2(右)をつける.同様に1(下)の座標情報を入手し,そこから行けるところに2(下)をつけていく.さらに2(右)の......と繰り返し,Gまでの最短時間を求めるのがBFSである.スタックと違い,1番下(古いデータ)から取り出すため,このような操作が出来るのだ.このようにして[tex:i(0≦i≦N)*3]からに行く場合の最短時間を求めれば,後はそれぞれの時間を足し合わせて出力すればいいというのは前述の通りだ.
プログラム
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
int bfs(int H, int W,
int sx = fac.at(i).first;
int sy = fac.at(i).second;
int gx = fac.at(i+1).first;
int gy = fac.at(i+1).second;
queue<P> que;
que.push(P(sx, sy));
dist.at(sx).at(sy) = 0;
while (que.size()) {
P gen = que.front();
que.pop();
if (gen.first == gx && gen.second == gy) {
break;
}
for(int i=0;i<4;i++) {
int nx = gen.first + dx.at(i);
int ny = gen.second + dy.at(i);
if(nx < 0 || ny < 0 || nx >= H || ny >= W) {
continue;
}
if(field.at(nx).at(ny) == 'X') {
continue;
}
if(dist.at(nx).at(ny) != 10000000) {
continue;
}
que.push(P(nx, ny));
dist.at(nx).at(ny) = dist.at(gen.first).at(gen.second) + 1;
}
}
return dist.at(gx).at(gy);
}
int main() {
int H, W, N;
cin >> H >> W >> N;
for(int i=0;i<H;i++) {
for(int j=0;j<W;j++) {
cin >> field.at(i).at(j);
}
}
for(int i=0;i<H;i++) {
for(int j=0;j<W;j++) {
if(field.at(i).at(j) == 'S') {
fac.at(0).first = i;
fac.at(0).second = j;
}
}
}
for(int k=0;k<N;k++) {
for(int i=0;i<H;i++) {
for(int j=0;j<W;j++) {
if(field.at(i).at(j) == '0' + (k+1)) {
fac.at(k+1).first = i;
fac.at(k+1).second = j;
}
}
}
}
int count = 0
for(int i=0;i<N;i++) {
count += bfs(H, W,
field,
fac, i);
}
cout << count << endl;
}
