AOJ 1290 Traveling Cube

Traveling Cube
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1290

問題概要

色がついたサイコロがあって、
床の色とサイコロのてっぺんの色が同じでないといけない。
白い床は自由にたどれる。
ある、色の順にたどりたいとき最短何手でたどることができるか。

解法

BFS。
訪れたかの判定はサイコロの状態と何文字目まで辿ったかもちゃんと記録する。

ソースの一部

int BFS(int sy, int sx){
  set<Dice> S[N][N][6];
  S[sy][sx][0].insert(Dice());
  queue<State> Q;
  for(Q.push((State){Dice(),0, sy, sx, 0});!Q.empty();Q.pop()){
    State now = Q.front();
    if(now.now == (int)s.length())return now.cost;
    if(now.toN()){
      if(S[now.y][now.x][now.now].find(now.d) == S[now.y][now.x][now.now].end()){
        Q.push(now);
        S[now.y][now.x][now.now].insert(now.d);
      }
    }
    now = Q.front();
    if(now.toE()){
      if(S[now.y][now.x][now.now].find(now.d) == S[now.y][now.x][now.now].end()){
        Q.push(now);
        S[now.y][now.x][now.now].insert(now.d);
      }
    }
    now = Q.front();
    if(now.toW()){
      if(S[now.y][now.x][now.now].find(now.d) == S[now.y][now.x][now.now].end()){
        Q.push(now);
        S[now.y][now.x][now.now].insert(now.d);
      }
    }
    now = Q.front();
    if(now.toS()){
      if(S[now.y][now.x][now.now].find(now.d) == S[now.y][now.x][now.now].end()){
        Q.push(now);
        S[now.y][now.x][now.now].insert(now.d);
      }
    }
  }
  return -1;
}

int main(){
  while(cin >> w >> h){
    if(w == 0 && h == 0)break;
    int sy, sx;
    rep(i, h){
      rep(j, w){
        cin >> t[i][j];
        if(t[i][j] == '#'){
          sy = i;
          sx = j;
          t[i][j] = 'w';
        }
      }
    }
    cin >> s;
    int res = BFS(sy, sx);
    if(res < 0){
      cout << "unreachable" << endl;
    }
    else cout <<res << endl;
  }
}