skyaozoraの日記

AOJ1178 壊れたドア

15:22

2011年ICPC国内予選のG問題。問題文はこ↑こ↓

他にも解法があるみたいだけどとりあえずそのうちの一つを。

まず全てのドアについて、「このドアが壊れていた時、それぞれのマスからゴールまで何枚カードキーが必要か」をBFSで求めておく。そのあと、各マスから移動する時に、「通過しようとしたドアが壊れていた場合」と「ドアが壊れてなくて次のマスに進めた場合」のうち悪い方に移るものとして、各マスからゴールまでに要するカードキーの枚数をベルマンフォードっぽく求める。

//ICPC国内予選11G 壊れたドア(AOJ1178)
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
string ma[62];
int di[62][62][32][32];
int dp[32][32];
vector<pint> now,ne,cl;
int h,w,inf=114514;
bool in(int x,int y){
	return (x>=0 && y>=0 && x<h && y<w);
}
void aedge(int a,int b,int x,int y,int i){
	if(di[a][b][x][y]<=i) return;
	di[a][b][x][y]=i;
	ne.pb(mp(x,y));
}
int cal(void){
	now=ne=cl;getline(cin,ma[0]);
	rep(i,h*2-1) getline(cin,ma[i]);
	rep(i,h*2-1) rep(j,w*2-1){
		if((i*j)%2>0 || (i+j)%2==0) continue;
		if(ma[i][j]=='1') continue;
		ma[i][j]='1';
		rep(k,h) rep(l,w) di[i][j][k][l]=inf;
		aedge(i,j,h-1,w-1,0);
		for(int k=0;ne.size();k++){
			now=ne;ne=cl;
			rep(l,now.size()){
				int x=now[l].fi,y=now[l].se;
				rep(m,4){
					int nx=x+dx[m],ny=y+dy[m];
					if(!in(nx,ny)) continue;
					if(ma[x+nx][y+ny]=='1') continue;
					aedge(i,j,nx,ny,k+1);
				}
			}
		}
		if(di[i][j][0][0]>=inf) return -1;
		ma[i][j]='0';
	}
	rep(i,h) rep(j,w) dp[i][j]=inf;dp[h-1][w-1]=0;
	rep(i,2710) rep(j,h) rep(k,w) rep(l,4){
		int nx=j+dx[l],ny=k+dy[l];
		if(!in(nx,ny)) continue;if(ma[j+nx][k+ny]=='1') continue;
		dp[j][k]=min(dp[j][k],max(dp[nx][ny]+1,di[j+nx][k+ny][j][k]));
	}
	return dp[0][0];
}
int main()
{
 	while(cin>>h>>w,h) cout<<cal()<<endl;
}

SRM462DIV1Hard WarTransportationも似たような問題。