Problem 1038 : Dr. Nakamura's Lab.

AOJ

問題概要

日本語なので詳しくは本文参照。
（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1038）

#####
##@##
#wc.#
#Ew.#
#####

みたいな部屋が与えられる。@は博士・Eは出口・cはコンテナ・wはパネル。
幅10以下高さ10以下。
かつwとcの個数はそれぞれ3つ以下である。

  • 博士は上下左右の'.'または'E'のマスに一歩ずつ動ける。
  • 浮いているコンテナは押すと壁か別のコンテナに当たるまで動き続ける
  • 押されたコンテナがパネルの上を通過した場合両者は消滅する
  • 博士がいなくなったおよび、コンテナおよびパネルがなくなった後のマスは'.'になる。

博士がEにつくまでの最小の歩数を求めよ。

解法

博士の位置・コンテナ1〜3の位置・パネル1〜3の位置をノードとしたダイクストラ法。
パネルはせいぜい2〜3回程度しか押せないため、全状態数は10000通り位である。


また、ダイクストラ法なのだが、queueに入れられる状態は(歩数+1)になっているものか(歩数±0)のものなので、priority_queueの代わりにdequeを使ってダイクストラすることができる。
（すなわち、歩数が増えた場合キューの後ろにノードを追加・歩数が増えない場合キューの先頭にノードを追加する）

ソースコード

1600byteの人とか居るけどどういうコードなんだろう……

int dy[]={-1,0,1,0},dx[]={0,-1,0,1};

int h,w,ey,ex;
char room[10][11];
struct S{
	int y,x,nc,np;
	pi c[3],p[3];
	bool operator<(const S &r)const
	{
		if(y!=r.y)return y<r.y;
		if(x!=r.x)return x<r.x;
		if(nc!=r.nc)return nc<r.nc;
		rep(i,nc)if(c[i]!=r.c[i])return c[i]<r.c[i];
		if(np!=r.np)return np<r.np;
		rep(i,np)if(p[i]!=r.p[i])return p[i]<r.p[i];
		return 0;
	}
};
int solve(S s)
{
	set<S> V; V.insert(s);
	deque<pair<int,S> >Q; Q.pb(mp(0,s));
	
	while(!Q.empty())
	{
		int cc=Q.front().first;
		s=Q.front().second; Q.pop_front();
		
		if(s.y==ey&&s.x==ex)return cc;
		
		//move
		rep(d,4)
		{
			S ns=s;
			ns.y=s.y+dy[d],ns.x=s.x+dx[d];
			if(room[ns.y][ns.x]=='#')continue;
			rep(i,s.nc)if(mp(ns.y,ns.x)==s.c[i])goto FAIL;
			rep(i,s.np)if(mp(ns.y,ns.x)==s.p[i])goto FAIL;
			
			if(V.count(ns))continue;
			V.insert(ns); Q.pb(mp(cc+1,ns));
			FAIL:;
		}
		//push
		rep(d,4)
		{
			S ns=s;
			int ny=s.y+dy[d],nx=s.x+dx[d],c=0;
			for(;c<s.nc;c++)if(mp(ny,nx)==s.c[c])break;
			if(c==s.nc)continue;
			
			int cy=ny,cx=nx,p=-1;
			while(1)
			{
				ny+=dy[d]; nx+=dx[d];
				if(room[ny][nx]=='#')break;
				rep(i,s.nc)if(mp(ny,nx)==s.c[i])goto END;
				rep(i,s.np)if(mp(ny,nx)==s.p[i])
				{
					p=i; goto END;
				}
				cy=ny; cx=nx;
			}
			END:
			if(p!=-1)
			{
				for(int i=c;i<s.nc-1;i++)ns.c[i]=ns.c[i+1];
				for(int i=p;i<s.np-1;i++)ns.p[i]=ns.p[i+1];
				ns.nc--; ns.np--;
				
				if(!V.count(ns))V.insert(ns),Q.push_front(mp(cc,ns));
			}
			else if(mp(cy,cx)!=s.c[c])
			{
				ns.c[c]=mp(cy,cx);
				if(!V.count(ns))V.insert(ns),Q.push_front(mp(cc,ns));
			}
		}
	}
	return -1;
}
int main()
{
	while(scanf("%d%d",&h,&w),h)
	{
		S s; s.nc=s.np=0;
		rep(i,h)
		{
			scanf("%s",room[i]);
			rep(j,w)
			{
				char &c=room[i][j];
				if(c=='c')s.c[s.nc++]=mp(i,j),c='.';
				else if(c=='w')s.p[s.np++]=mp(i,j),c='.';
				else if(c=='@')s.y=i,s.x=j,c='.';
				else if(c=='E')ey=i,ex=j,c='.';
			}
		}
		printf("%d\n",solve(s));
	}
	return 0;
}