ABC176に参加してみた
初めに
ABC176はABC完でした。D問題までは到達したのですが、
目をつむって考えていて、気づいたら朝になっていましたorz(寝落ち)
まぁ起きていても解けた問題では無かったのですが(笑)
今回はD問題について書いてきますが、自分の理解を深める事に重点を置いて書いて行きます。
(いつもそうですが今回は特に)
https://atcoder.jp/contests/abc176
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - Step
この問題は迷路のスタート地点からゴール地点に到達するまでに
必要な最小のワープ回数を回答するという問題です。
解説を見てからの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
// 4近傍の座標への移動をするために使用
const ll di[] = {-1, 0, 1, 0};
const ll dj[] = {0, -1, 0, 1};
typedef pair<ll,ll> Pair;
int main(){
ll H, W;
ll Ch, Cw;
ll Dh, Dw;
cin >> H >> W;
cin >> Ch >> Cw;
//扱いやすいように0起算の形にしています。
Ch--;Cw--;
cin >> Dh >> Dw;
//扱いやすいように0起算の形にしています。
Dh--;Dw--;
vector<string> S(H);
for (ll i = 0; i < H;++i)
cin >> S[i];
// 距離を格納する配列
vector<vector<ll>> dist(H, vector<ll>(W, INF));
// ある地点から行けるマスを格納
deque<Pair> q;
// 初期値の距離はコスト0で初期化
dist[Ch][Cw] = 0;
// 初期値をキューに格納
q.emplace_back(Ch,Cw);
// キューが空になるまでループを回す。
while(!q.empty()){
// i,jにキューの先頭の座標を格納
ll i = q.front().first;
ll j = q.front().second;
// 移動元の座標のコストを格納
ll d = dist[i][j];
// キューから先頭の座標を取り除きます。
q.pop_front();
// コスト0で移動できる場所(上下左右)
for (ll ii = 0; ii < 4;++ii){
// 上下左右の四近傍の座標を格納
ll ni = i + di[ii];
ll nj = j + dj[ii];
// 迷路の枠外の座標だった場合はスキップ
if(nj < 0 || ni < 0 || ni >= H || nj >= W)
continue;
// 壁のある座標だったらスキップ
if (S[ni][nj] == '#')
continue;
// 座標の移動コストがd以下だったらスキップ
if (dist[ni][nj] <= d)
continue;
// 座標のコストをdに更新
dist[ni][nj] = d;
// キューの先頭に座標を格納
q.emplace_front(ni,nj);
}
// コスト1で移動できる場所(ワープ魔法を使用した場合の5×5マス)
for (ll ei = -2; ei <= 2;++ei)
{
for (ll ej = -2; ej <= 2;++ej)
{
// 現在いる座標の5×5マス座標を格納
ll ni = i + ei;
ll nj = j + ej;
// 迷路の枠外の座標だった場合はスキップ
if(nj < 0 || ni < 0 || ni >= H || nj >= W)
continue;
// 壁のある座標だったらスキップ
if (S[ni][nj] == '#')
continue;
// 座標の移動コストがd+1以下だったらスキップ
if (dist[ni][nj] <= d+1)
continue;
// 座標のコストをd+1に更新
dist[ni][nj] = d+1;
// キューの末尾に座標を格納
q.emplace_back(ni,nj);
}
}
}
// 初期値から更新されていない場合はゴールに到達出来ないため-1を出力
if(dist[Dh][Dw] == INF)
cout << "-1" << endl;
// 初期値から更新されている場合はゴール地点の座標のコストを出力
else
cout << dist[Dh][Dw] << endl;
return 0;
}
この問題では01-BFSというアルゴリズムと利用することで、解くことが出来ます。
01-BFSは今回のように2通りの移動方法があるような場合に利用することが可能です。
BFSはキュー(queue)というデータ構造で実装を行うことができますが、
01-BFSはこれを拡張したものでデック(deque)というデータ構造で実装出来ます。
デック(deque)はキュー(queue)とは異なり両端からデータの出し入れを行う事が出来ます。
これを利用してコスト0で移動(魔法無し)できる座標を先頭に、
コスト1で移動(魔法有り)できる座標を末尾に追加することで
コスト0の座標が先頭に、コスト1の座標が末尾に固めっている状態とすることが出来ます。
このデータ構造を使用することで、コスト0で移動した座標を優先して探索が可能となります。
そして、コスト0の移動については現在いる座標を中心とした4近傍(上下左右)の座標、
コスト1の移動については現在いる座標を中心とした5×5マスの座標について距離を更新します。
（配列di,djのような形で定義しておくと、ループを回すことで4近傍の探索が行えます。下記参照）
距離の更新が完了したら、ゴールの初期値が更新されているか確認を行い、
更新がされていた場合はその距離を出力し、更新されていない場合は-1を出力することで
問題を解くことが出来ます。
最後に
知らないアルゴリズムが登場したらあきらめて次回出てきた場合には対応できるように
まとめておくしかないですね。まぁ後は寝落ちしないように頑張ります(笑)
