Problem 1038 : Dr. Nakamura's Lab.

Problem D: Dr. Nakamura's Lab.
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1038

• 問題概要

グリッドに通れないところがあって、グリッドにころがってるコンテナをすべらして当てると通れるようになって、コンテナが消える。
壁かコンテナか通れないところに当たるまで動き続ける。

出口にたどりつけるまでのコストをもとめよ。

• 解法

普通にBFS。
非常に書いてて楽しい！
状態は、パネルの位置、コンテナの位置、自分の位置ｄでいいんじゃないんでしょうか。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

bool t[10][10];
int h, w, dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};

class State{
public:
  int x, y, px[3], py[3], cx[3], cy[3], cost;
  bool operator < (const State &s)const{
    if(x != s.x)return x < s.x;
    if(y != s.y)return y < s.y;
    rep(i, 3){
      if(px[i] != s.px[i])return px[i] < s.px[i];
      if(cx[i] != s.cx[i])return cx[i] < s.cx[i];  
      if(py[i] != s.py[i])return py[i] < s.py[i];
      if(cy[i] != s.cy[i])return cy[i] < s.cy[i];
    }
    return false;
  }
  State(){
    rep(i, 3){
      px[i] = py[i] = cx[i] = cy[i] = -1;
    }
    cost = 0;
  }
  bool move(int d){
    int nx = x + dx[d], ny = y + dy[d];
    if(!t[ny][nx])return false;
    rep(i, 3){
      if(px[i] == nx && py[i] == ny)return false;
      if(cx[i] == nx && cy[i] == ny)return false;
    }
    cost++;
    x = nx;
    y = ny;
    return true;
  }
  bool push(int d){
    int nx = x +dx[d], ny = y + dy[d], id; 
    bool found = false;
    rep(i, 3){
      if(cx[i] == nx && cy[i] == ny){
	id = i;
	found = true;
      }
    }
    if(!found)return false;

    while(1){    
      nx += dx[d];
      ny += dy[d];
      rep(i, 3){
	if(px[i] == nx && py[i] == ny){
	  cx[id] = -1;
	  cy[id] = -1;
	  px[i] = -1;
	  py[i] = -1;
	  return true;
	}
	if((cx[i] == nx && cy[i] == ny) || !t[ny][nx]){
	  cx[id] = nx - dx[d];
	  cy[id] = ny - dy[d];
	  return true;
	}
      }  
    }
    return false;
  }
};
  


main(){

  while(cin >> h >> w){
    if(h + w == 0)break;
    int cp = 0, cc = 0, gx, gy;
    State s;
    rep(i, h){
      rep(j, w){
	t[i][j] = true;
	char c;
	cin >> c;
	if(c == '#'){
	  t[i][j] = false;
	}
	if(c == 'w'){
	  s.px[cp] = j;
	  s.py[cp] = i;
	  cp++;
	}
	if(c == 'c'){
	  s.cx[cc] = j;
	  s.cy[cc] = i;
	  cc++;
	}
	if(c == '@'){
	  s.x = j;
	  s.y = i;
	}
	if(c == 'E'){
	  gx = j;
	  gy = i;
	}
      }
    }

    set<State> visited;
    queue<State> Q;
    Q.push(s);
    int ans = -1;
    while(!Q.empty()){  
      s = Q.front();
      if(s.x == gx && s.y == gy){
	ans = s.cost;
	break;
      }
      Q.pop();
      if(visited.find(s) != visited.end())continue;
      visited.insert(s);
      rep(i, 4){
	State now = s;
	if(now.push(i)){
	  Q.push(now);
	}
      }
      rep(i, 4){
	State now = s;
	if(now.move(i)){
	  Q.push(now);
	}
      }
    }
    cout << ans << endl;
  }
}