AOJ 1329: Sliding Block Puzzle

こういうやるだけ全力疾走系好きなのでこういう問題だけでコンテスト開いてくれませんか。
20分くらい

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
char str[60][60];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int bfs[60][60];
int ijk[60][60][4];
int v[60][60][4];
int dis[2][2];
int a,b;
int calc(vector<pair<int,int> >st,vector<pair<int,int> >go,int xr,int xc){
	for(int l=0;l<2;l++){
		for(int j=0;j<a;j++)for(int k=0;k<b;k++)bfs[j][k]=99999999;
		bfs[st[l].first][st[l].second]=0;
		queue<pair<int,int> >Q;
		Q.push(make_pair(st[l].first,st[l].second));
		while(Q.size()){
			int row=Q.front().first;
			int col=Q.front().second;
			Q.pop();
			for(int j=0;j<4;j++){
				int tr=row+dx[j];int tc=col+dy[j];
				if(tr<0||tc<0||tr>=a||tc>=b)continue;
				if(str[tr][tc]=='*')continue;
				if(tr==xr&&tc==xc)continue;
				if(tr==xr+1&&tc==xc)continue;
				if(tr==xr&&tc==xc+1)continue;
				if(tr==xr+1&&tc==xc+1)continue;
				if(bfs[tr][tc]>bfs[row][col]+1){
					bfs[tr][tc]=bfs[row][col]+1;
					Q.push(make_pair(tr,tc));
				}
			}
		}
		dis[l][0]=bfs[go[0].first][go[0].second];
		dis[l][1]=bfs[go[1].first][go[1].second];
	}
	return min(dis[0][0]+dis[1][1],dis[0][1]+dis[1][0]);
}
int main(){
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<a;i++)scanf("%s",str[i]);
		for(int i=0;i<a;i++)for(int j=0;j<b;j++)for(int k=0;k<4;k++){
			ijk[i][j][k]=999999999;
			v[i][j][k]=0;
		}
		int sr,sc;
		for(int i=0;i<a;i++)for(int j=0;j<b;j++){
			if(str[i][j]=='X'){
				sr=i;sc=j;
			}
		}
		sr--;sc--;
		priority_queue<pair<int,pair<pair<int,int>,int> > >Q;
		for(int i=0;i<4;i++){
			vector<pair<int,int> >st;
			for(int j=0;j<a;j++)for(int k=0;k<b;k++)if(str[j][k]=='.'){
				st.push_back(make_pair(j,k));
			}
			vector<pair<int,int> >go;
			if(i==0){go.push_back(make_pair(sr,sc+2));go.push_back(make_pair(sr+1,sc+2));}
			if(i==1){go.push_back(make_pair(sr+2,sc));go.push_back(make_pair(sr+2,sc+1));}
			if(i==2){go.push_back(make_pair(sr,sc-1));go.push_back(make_pair(sr+1,sc-1));}
			if(i==3){go.push_back(make_pair(sr-1,sc));go.push_back(make_pair(sr-1,sc+1));}
			int co=calc(st,go,sr,sc);
			if(co<99999999){
				ijk[sr][sc][i]=co;
				Q.push(make_pair(-co,make_pair(make_pair(sr,sc),i)));
			}
		}
		while(Q.size()){
			int cost=-Q.top().first;
			int row=Q.top().second.first.first;
			int col=Q.top().second.first.second;
			int dir=Q.top().second.second;
			Q.pop();
			if(v[row][col][dir])continue;
			v[row][col][dir]=1;
			vector<pair<int,int> >st;
			if(dir==0){st.push_back(make_pair(row,col+2));st.push_back(make_pair(row+1,col+2));}
			if(dir==1){st.push_back(make_pair(row+2,col));st.push_back(make_pair(row+2,col+1));}
			if(dir==2){st.push_back(make_pair(row,col-1));st.push_back(make_pair(row+1,col-1));}
			if(dir==3){st.push_back(make_pair(row-1,col));st.push_back(make_pair(row-1,col+1));}
			for(int i=0;i<4;i++){
				if(v[row][col][i])continue;
				vector<pair<int,int> >go;
				if(i==0){go.push_back(make_pair(row,col+2));go.push_back(make_pair(row+1,col+2));}
				if(i==1){go.push_back(make_pair(row+2,col));go.push_back(make_pair(row+2,col+1));}
				if(i==2){go.push_back(make_pair(row,col-1));go.push_back(make_pair(row+1,col-1));}
				if(i==3){go.push_back(make_pair(row-1,col));go.push_back(make_pair(row-1,col+1));}
				int co=calc(st,go,row,col);
				if(!v[row][col][i]&&ijk[row][col][i]>cost+co){
					ijk[row][col][i]=cost+co;
					Q.push(make_pair(-cost-co,make_pair(make_pair(row,col),i)));
				}
			}
			if(!v[row+dx[dir]][col+dy[dir]][dir^2]&&ijk[row+dx[dir]][col+dy[dir]][dir^2]>cost+1){
				ijk[row+dx[dir]][col+dy[dir]][dir^2]=cost+1;
				Q.push(make_pair(-cost-1,make_pair(make_pair(row+dx[dir],col+dy[dir]),dir^2)));
			}
		}
		int ret=999999999;
		for(int i=0;i<4;i++){
			ret=min(ret,ijk[0][0][i]);
		}
		if(ret>9999999)printf("-1\n");
		else printf("%d\n",ret);
	}
}