AOJ0037 Path on a Grid
問題
格子状の経路 | Aizu Online Judge
右手法で壁をつたう。はじめの位置からスタートして、元の位置に戻ってくるまでの移動方向を逐次出力せよ。
詳しくはリンク先の図と入出力を見て下さい。
解法
まず、グリッドを動くのではなくて、線分上を動くことに注意する。以下の問題と入力が似ているからといって騙されてはならない。
Amazing Mazes | Aizu Online Judge
格子点を順に番号付けして、(i, j)の点をi * 5 + j番として、グラフを張る。この時、辺を利用可能な場合の向きの制約を辺に加えておく。
右手法によると、移動の仕方には以下の4パターンが存在する。
1. 左に回転する移動
2. 真っ直ぐ進む移動
3. 右に回転する移動
4. 後ろに戻る移動
4番目の移動方法は見逃しやすいので注意。
あとは、初期位置から右を向いて経路を順に辿り、左を向いて初期位置に戻るまで方向を出力すれば良い。
int dx[4] = {-1,0,1,0}, dy[4] = {0,-1,0,1}; vector<pair<int, int>> G[55]; int main() { rep(i, 5) { char x; rep(j, 4) { cin >> x; if(x-'0') { G[i * 5 + j].emplace_back(i * 5 + j + 1, 2); G[i * 5 + j + 1].emplace_back(i * 5 + j, 0); } } if(i == 4) break; rep(j, 5) { cin >> x; if(x-'0') { G[i * 5 + j].emplace_back((i + 1) * 5 + j, 3); G[(i + 1) * 5 + j].emplace_back(i * 5 + j, 1); } } } string const OP = "LURD"; int y = 0, x = 0, d = 2; while(y != 0 || x != 0 || d != 0) { int le = -1, st = -1, ri = -1, dw = -1; for(auto && e: G[y * 5 + x]) { if(e.second == (d + 3) % 4) le = e.second; if(e.second == (d + 1) % 4) ri = e.second; if(e.second == d) st = e.second; if(e.second == (d + 2) % 4) dw = e.second; } if(le != -1) d = le; else if(st != -1) ; else if(ri != -1) d = ri; else d = dw; y += dy[d], x += dx[d]; cout << OP[d]; } cout << endl; return 0; }