AtCoder Regular Contest 005_C_器物損壊！高橋君
0-1BFSの問題.障害は多い方が燃えるよね.
問題の説明
高橋君はの迷路を移動する.高橋君は2回まで障害物を乗り越えられるものとして,ゴールに辿り着けるかを判定せよ.
条件
考えた事
迷路の基本的な実装は,
BFSについては,
を参考にしてもらいたい.手数がいらない,つまり何手で迷路にゴール出来るかは考えなくていいというのは後述する大きなポイントであり,DFSに似通っている.
ただ,それとの大きな違いとしては2回まで塀を超えられる事だろう.今までならばとりあえず深く探索し,行く先全て塀で塞がれていたらそれでおしまい,別のルートを探る方針であった.今回は二回まで塀を乗り越えられるため,それでは終わらない.
どう考えるべきだろうか.答えは塀を乗り越えた回数で移動経路をカウントするべきだろう.つまり塀を乗り越えた回数が0回のところは全て0と記し,1回乗り越えて行ける場所は1,2回ならば2......というようにやり,ゴールまでに乗り越えた塀の数が2回以下かどうかで判定をすればいい.
図のようなイメージをもてばいいだろう.青で記した部分が塀を乗り越えた回数である.これは上にあるチーズのBFSとは少し違う.あちらでも自分が次に行けるところにdist配列を用いて番号を振っていったが,その時は行ける場所は(現在の手数)+1とし続けていた.対してこちらは塀を乗り越えずに行ける箇所は+1としていない.
つまり,BFSでは移動コストが常に1である一方,この問題は0である時と1である時が混在する.そのため,このアルゴリズムの事を0-1BFSと表記するのだ.*1
考え方の説明はこの辺にして,この問題はどう実装すべきだろうか.
こういう時は直感を大事にしたい.実際に君がこの迷路を解くとしよう.目の前の壁,すぐ乗り越えますか?乗り越えた先に希望があるとは限らない.苦難を乗り越えたからといって幸せになれる保証はない.まずは穏便に,穏健に,今の状況で行けるところを全て探索するだろう.そうした上で行き詰って初めて壁を打破するのが普通である.*2
今回の問題も同様である.目の前に塀があるからといってぽんぽんぽんぽん乗り越えたとて,それが最善である保障は全くない.右の突き当りの塀を1回だけ乗り越えたら着くかもしれない.なるべく塀は乗り越えたくはないのだ.体力と関節に不安のない小学生ならいざ知らず,大人であり,かつ松潤やキムタクみたいに塀を乗り越える事が絵になるような人種でない私たちは,落ち着いて,老練に全部見てから検討すればいい.重ね重ねであるが塀はあまり乗り越えたくないのだ.ぎっぐり腰なるかもしれないし.
閑話休題.つまりどうすべきか.塀を乗り越える必要がある場合をなるだけ後回しにして,乗り越えずにいけるものを先に試せばいい.このように先端と末尾の両方に格納し,取り出せるデータ構造としてdeque(両端キュー) が存在する.0-1BFSではそれを採用する.コスト0で出来るものを先に,コスト1かかるものを後に回し,探索していくのである.
deque<P> que;
que.push_front(P(sx, sy));
dist.at(sx).at(sy) = 0;
if (field.at(nx).at(ny) != '#')
{
if (dist.at(nx).at(ny) > dist.at(gen.first).at(gen.second))
{
dist.at(nx).at(ny) = dist.at(gen.first).at(gen.second);
que.push_front(P(nx, ny));
}
行く先に塀がなければそこはコスト0で行ける部分であるので,dist配列(今回では,塀を乗り越えた回数を記録するもの)には今いるところと同様の数字を入れて対応する.*3
そしてpush_frontとして前端に格納している.これによって移動コストが同等のものを先に扱えるようにしている.
else
{
if (dist.at(nx).at(ny) > dist.at(gen.first).at(gen.second) + 1)
{
dist.at(nx).at(ny) = dist.at(gen.first).at(gen.second) + 1;
que.push_back(P(nx, ny));
行く先に塀がある場合は,今いるところから1増やした数字を入れて対応する.そしてこちらはpush_backとして末端に格納している.こうする事でコストの低い順に扱えるのだ.
迷路の途中でdequeの中身が無くなって移動コストが高い方が先に扱われるのではないかと不安がる人もいるかもしれない.しかし,今回塀は乗り越えたくないが乗り越えても"いい"事に目がいけばそうならないのは明らかだろう.
また,if文とdequeの合わせ技でなるべくコストの小さい順に処理し,もしコストがかかるとしても最小限に抑えられる事も分かるだろう.言われてみれば当たり前であるが,移動コストの最小値は,その塀の隣接上下左右にあるマスの移動コストの最小値+0or+1である.だから数字の小さい順に調べる事に合理性があるのだ.
本当に繰り返しになるが,なるべく塀を乗り越えず,コストの低い順に扱いたい.それを実現するのが0-1BFSなのである.
プログラム
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
int bfs(int H, int W,
int sx, int sy,
int gx, int gy,
{
deque<P> que;
que.push_front(P(sx, sy));
dist.at(sx).at(sy) = 0;
while (que.size())
{
P gen = que.front();
que.pop_front();
if (gen.first == gx && gen.second == gy)
{
break;
}
for (int i = 0; i < 4; i++)
{
int nx = gen.first + dy.at(i);
int ny = gen.second + dx.at(i);
if (nx < 0 || ny < 0 || nx >= H || ny >= W)
{
continue;
}
if (field.at(nx).at(ny) != '#')
{
if (dist.at(nx).at(ny) > dist.at(gen.first).at(gen.second))
{
dist.at(nx).at(ny) = dist.at(gen.first).at(gen.second);
que.push_front(P(nx, ny));
}
}
else
{
if (dist.at(nx).at(ny) > dist.at(gen.first).at(gen.second) + 1)
{
dist.at(nx).at(ny) = dist.at(gen.first).at(gen.second) + 1;
que.push_back(P(nx, ny));
}
}
}
}
return dist.at(gx).at(gy);
}
int main()
{
int H, W;
cin >> H >> W;
int sx, sy, gx, gy;
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')
{
sx = i;
sy = j;
}
if (field.at(i).at(j) == 'g')
{
gx = i;
gy = j;
}
}
}
int res = bfs(H, W,
sx, sy,
gx, gy,
field);
if (res <= 2)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
