TopCoder SRM 385 Div1 Medium TurningMaze

TopCoder 探索

問題

hxwのマスで表される迷路がある。
それぞれのマスは

  • 'A'は壁が四方にないこと
  • 'B'は壁が四方全部にあること
  • 'C'は壁が左右方向にだけあること
  • 'D'は壁が上下方向にだけあること

を意味する。


左上のマスを出発して、右下のマスまで辿り着きたい。
1ターンに、壁のない方向のマスに移動するか、次の回転操作のどちらかを行うことができる。
右下のマスに辿り着くのに必票な時間の最小値を求めよ。
右下のマスにどうやっても辿り着くことが出来ない場合、-1を返せ。


ただし、グリッドの外にはみでてはならないものとする。


回転操作：
自分のいる列のマスを全て時計回りに回転させ、自分のいる行のマスを全て時計周りに回転させる。

制約条件

行,列≦7

方針

自明に無理だったら（C,Dのマスをのマスとみなしても右下のマスに辿り着けない）
その時点で-1を返す。


無理じゃなかったら、A*探索をする。
ゴールまでの距離の推定値はマンハッタン距離を使った。
また、A,Bのマスは回転させても意味がないので、状態に含めないようにする。
これで通ってしまった。


editorialでの解法は、
反転状態は、行と列のうち反転しているものの集合により一意に決まるので、
2^14個の状態を持つようにするというものだった。


なので、状態数は2^14*7*7個しかないっぽい。
これだったら何も考えないA*書いて通るのも納得。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
vs M;
int h,w;
bool ck(){
  queue<int> q;
  bool v[50][50]={};
  q.push(0);
  while(!q.empty()){
    int y=q.front()/w, x=q.front()%w; q.pop();
    v[y][x]=1;
    if(y==h-1&&x==w-1)return 1;
    rep(d,4){
      int ny=y+dy[d], nx=x+dx[d];
      if(ny<0||ny>=h||nx<0||nx>=w||v[ny][nx])continue;
      if(M[ny][nx]=='B')continue;
      q.push(ny*w+nx);
    }
  }
  return 0;
}
class TurningMaze {
  public:
  int minTime(vector <string> maze) {
    h=maze.size(); w=maze[0].size();
    M=maze;
    if(!ck())return -1;
    
    typedef pair<pi,pi> P; //guess, time, state, pos
    #define D(y,x) (h-y-1+w-x-1)
    priority_queue<P,vector<P>,greater<P> > q;
    set<pi> v;
    
    q.push(mp(mp(D(0,0),0),mp(0,0)));
    while(!q.empty()){
      int y=q.top().second.second/w,x=q.top().second.second%w;
      ll state=q.top().second.first;
      int t=q.top().first.second; q.pop();
      
      if(v.count(mp(state,y*w+x)))continue;
      v.insert(mp(state,y*w+x));
      
      if(y==h-1&&x==w-1)return t;
      
      rep(d,4){
        int ny=y+dy[d], nx=x+dx[d];
        if(ny<0||nx<0||ny>=h||nx>=w||v.count(mp(state,ny*w+nx)))
          continue;
        int cdir=M[y][x]-'C'^state>>y*w+x&1;
        int ndir=M[ny][nx]-'C'^state>>ny*w+nx&1;
        if(M[ny][nx]=='B'||M[y][x]!='A'&&cdir!=d%2||
          M[ny][nx]!='A'&&ndir!=d%2)continue;
        q.push(mp(mp(D(ny,nx)+t+1,t+1),mp(state,ny*w+nx)));
      }
      rep(i,h)if(M[i][x]=='C'||M[i][x]=='D')state^=1ll<<i*w+x;
      rep(i,w)if(M[y][i]=='C'||M[y][i]=='D')state^=1ll<<y*w+i;
      if(!v.count(mp(state,y*w+x)))
        q.push(mp(mp(D(y,x)+t+1,t+1),mp(state,y*w+x)));
    }
    return -1;
  }
};