1218 - Push!!

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

問題

図見れば分かる。
貨物を何回動かせばゴールに到達できるか。

解法

状態は人の座標と貨物の座標。
見た瞬間普通のBFSかと思って書いてWA。
人が動くのはコスト0だから、グラフで言えばコスト0の辺とコスト1の辺が混在してるグラフでの最短路。
よってpriority_queueを使ってダイクストラっぽくすればいい。
コスト1の辺だけだからこそBFSで最短コストを求められるというのを理解した。

それにしても、配列[y][x]ではなく配列[x][y]とする癖そろそろ直さないと・・・。

ソース

struct P {
  int x,y,cx,cy;
  int cost;
  P(int x,int y,int cx,int cy,int cost) : x(x),y(y),cx(cx),cy(cy),cost(cost) {}
};
const bool operator<(const P &a, const P &b) {
  return a.cost > b.cost;
}

bool visited[7][7][7][7];
int main() {
  int w,h;
  while(cin>>w>>h,w||h) {
    int ba[w][h];
    int sx,sy,cx,cy;
    REP(y,h) {
      REP(x,w) {
        cin >> ba[x][y];
        if (ba[x][y] == 4) {
          sx = x; sy = y;
        } else if (ba[x][y] == 2) {
          cx = x; cy = y;
        }
      }
    }
    priority_queue<P> Q;
    Q.push(P(sx,sy,cx,cy,0));
    memset(visited,0,sizeof(visited));
    const int dx[] = {-1,0,1,0};
    const int dy[] = {0,1,0,-1};
    int res = -1;
    while(!Q.empty()) {
      P now = Q.top(); Q.pop();
      int x=now.x,y=now.y,cx=now.cx,cy=now.cy,cost=now.cost;
      if (visited[x][y][cx][cy]) continue;
      visited[x][y][cx][cy] = 1;
      
      if (ba[cx][cy] == 3) {
        res = cost;
        break;
      }
      REP(k,4) {
        int xx = x+dx[k];
        int yy = y+dy[k];
        if (xx<0||xx>=w||yy<0||yy>=h) continue;
        if (ba[xx][yy] == 1) continue;
        if (xx==cx&&yy==cy) {
          // push
          int xxx = cx+dx[k];
          int yyy = cy+dy[k];
          if (xxx<0||xxx>=w||yyy<0||yyy>=h) continue;
          if (ba[xxx][yyy] == 1 || visited[x][y][xxx][yyy]) continue;
          Q.push(P(x,y,xxx,yyy,cost+1));
        } else {
          if (visited[xx][yy][cx][cy]) continue;
          // move;
          Q.push(P(xx,yy,cx,cy,cost));
        }
      }
    }
    cout << res << endl;
  }
}