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

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0037

格子状の経路 | Aizu Online Judge

あまり見慣れない問題で面食らってしまった. 各点に対して壁の方向を保存する方法に関して, 構造体を作るのがあまり綺麗でないと思ったので, 4bitの数で表現することにした. これでn*nの問題に対しても高速に対処できそう. あとは来た道を保存しておいて,左手から順番に時計回りに壁の有無を探索すればよい(右手法). 忘れがちなのが来た道を帰る条件で私はこれで暫く戸惑った.「もう一度戻る」という設定なのでdo-while文を使えば簡潔に書ける.

int a[35];

void solve()
{
  string ans = "";
  int pre, i, dir = 0, now = 0;
  int mov[] = {1,5,-1,-5};
  string c[] = {"R","D","L","U"};
  do
  {
    pre = (dir+2)%4;
    for(i=(pre+1)%4;i!=pre;++i%=4)
    {
      if(a[now]>>i&1)
      {
        dir = i;
        break;
      }
    }
    if(i == pre) dir = pre;
    ans += c[dir];
    now += mov[dir];
  }
  while(now != 0);
  cout << ans << "\n";
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  fill_n(a,35,0);
  string s; int c;
  REP(i,9)
  {
    cin >> s;
    c = i/2;
    if(i%2==0)
    {
      REP(j,4) if(s[j]=='1')
      {
        a[c*5+j] += 1;
        a[c*5+j+1] += 4;
      }
    }
    else
    {
      REP(j,5) if(s[j]=='1')
      {
        a[c*5+j] += 2;
        a[(c+1)*5+j] += 8;
      }
    }
  }
  solve();
  return 0;
}