読者です 読者をやめる 読者になる 読者になる

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;
}