AOJ1038 Dr. Nakamura's Lab.

解法

---

私の苗字じゃないですか!と思って前々からやりたかった問題。
最初priorityつけてたが,遅くなるだけじゃんって気づいて普通のqueでやったら通った。
枝刈りがうまくいかなくて大変だった。最終的には,強引にlonglong型に直して記憶した。
ソース長い。

ソース

---

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define fr first
#define sc second
#define rep(i,n) for(int i = 0 ; i < n ; i++ )
typedef pair< int , int > Pt;
typedef long long ll;
const int dx[] = { 0, 1, -1, 0}, dy[] = { 1, 0, 0, -1};
struct P{
  Pt nkmr;
  vector< Pt > pnl,cnt;
};
typedef pair< int , P > IP;
Pt Goal;
int h, w;
char mas[10][10];
int search_cnt(int y,int x,P& n){
  rep(i,n.cnt.size()) if(n.cnt[i] == Pt(y,x)) return i;
  return -1;
}
int search_panel(int y,int x,P& n){
  rep(i,n.pnl.size()) if(n.pnl[i] == Pt(y,x)) return i;
  return -1;
}
bool isused(map<ll,bool>& used,P& p){
  ll ret = (p.nkmr.fr << 4) + p.nkmr.sc;
  rep(i,p.pnl.size()){
    ret <<= 4;
    ret += p.pnl[i].fr;
    ret <<= 4;
    ret += p.pnl[i].sc;
  }
  rep(i,p.cnt.size()){
    ret <<= 4;
    ret += p.cnt[i].fr;
    ret <<= 4;
    ret += p.cnt[i].sc;
  }
  if(used[ret]++) return true;
  return false;
}
int bfs(P& St){
  queue<pair< int , P > > que;
  map < ll , bool >  used;
  que.push(IP(0,St));
  while(!que.empty()){
    int _cost = que.front().fr;
    P p = que.front().sc;
    que.pop();
    if(p.nkmr == Goal) return _cost;
    if(isused(used,p)) continue;
    rep(i,4){
      P next = p;
      int ny = p.nkmr.fr + dy[i], nx = p.nkmr.sc + dx[i],contena,panel;
      if(mas[ny][nx] == '#' || search_panel(ny,nx,next) != -1) continue;
      if((contena = search_cnt(ny,nx,next)) != -1){ //コンテナあった
        int ty = ny + dy[i], tx = nx + dx[i];
        if(mas[ty][tx] != '.' || search_cnt(ty,tx,next) != -1) continue;
        while(mas[ty][tx] == '.' &&
              search_cnt(ty,tx,next) == -1 && search_panel(ty,tx,next) == -1){
          ty += dy[i], tx += dx[i];
        }
        if((panel = search_panel(ty,tx,next)) != -1){
          next.cnt[contena] = Pt(-1,-1), next.pnl[panel] = Pt(-1,-1);
        }else next.cnt[contena] = Pt(ty - dy[i],tx - dx[i]);
        que.push(IP(_cost,next));
      }else que.push(IP(_cost+1,(P){Pt(ny,nx),p.pnl,p.cnt}));
    }
  }
  return -1;
}
int main(){
  while(cin >> h >> w , h ){
    P p = (P){Pt(),vector<Pt>(),vector<Pt>()};
    rep(i,h) rep(j,w){
      cin >> mas[i][j];
      if(mas[i][j] == '@') p.nkmr = Pt(i,j), mas[i][j] = '.';
      else if(mas[i][j] == 'w'){
        p.pnl.push_back(Pt(i,j)), mas[i][j] = '.';
      }else if(mas[i][j] == 'c'){
        p.cnt.push_back(Pt(i,j)), mas[i][j] = '.';
      }else if(mas[i][j] == 'E') Goal = Pt(i,j), mas[i][j] = '.';
    }
    cout << bfs(p) << endl;
  }
}