TopCoder SRM 267 Div1 Medium ValetParking

問題

100x100のスライドパズルがある。
最初(emptyRow,emptyCol)のマスが空白である。
(carRow,carCol)のマスを(0,0)に移動させるのに最小で何手かかるか求めよ。

スライドパズルは、ピースと空白を入れ替える操作のみが出来て、
ピースを外に出したり、重ねたりしてはならない。

制約条件

座標は正しい。

方針

幅優先探索。であるが、状態を(空白のマスの座標、目的のピースの座標）とすると、
状態数が100^4になって、時間的にも空間的にも計算量が間に合わない。

多分A*探索をしてもダメ。

ここで、空白のマスは、目的のピースの周囲4マスにいる場合以外を考慮しなくていいことに注目する。
すると、状態数が100^2*4になり、制限時間内に解けるようになる。

こういう、典型問に少しだけ工夫するという系の問題が全然解けないように感じる。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
inline void push(priority_queue<pi> &q,map<int,int> &s,int ay,int ax,int by,int bx,int c){
  int n=ay*1000000+ax*10000+by*100+bx;
  if(s.count(n)&&s[n]<=c)return;
  s[n]=c;
  q.push(mp(-c,n));
}
int dist(int ay,int ax,int by,int bx,int cy,int cx){
  int ret=abs(ay-by)+abs(ax-bx);
  if(ay==by&&ay==cy&&(ax<cx)!=(bx<cx))return ret+2;
  if(ax==bx&&ax==cx&&(ay<cy)!=(by<cy))return ret+2;
  return ret;
}
class ValetParking {
  public:
  int minMoves(int er, int ec, int cr, int cc) {
    map<int,int> s;
    priority_queue<pi> q;
    push(q,s,er,ec,cr,cc,0);
    while(!q.empty()){
      er=q.top().second/1000000; ec=q.top().second/10000%100;
      cr=q.top().second/100%100; cc=q.top().second%100;
      int c=-q.top().first; q.pop();
      if(cr==0&&cc==0)return c;
      if(abs(er-cr)+abs(ec-cc)==1)push(q,s,cr,cc,er,ec,c+1);
      rep(d,4){
        int y=cr+dy[d],x=cc+dx[d];
        if(y<0||x<0||y>99||x>99)continue;
        push(q,s,y,x,cr,cc,c+dist(er,ec,y,x,cr,cc));
      }
    }
    return -1;
  }
};