AOJ 2319: ソウルジェムゲーム

前半パートは解説参照。
多項式でできます。
dp[i][j][k][l][m]: i段目、Sがj列、Kがk列にいる。1個前のときSはl列に居た。満たすべき条件二つはmで管理。

場合わけが多すぎてかなり大変。

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[12][12];
int dp[12][12][12][12][4];
int H,W;
int sr,sc,kr,kc,SR,SC,KR,KC;
inline int ABS(int a){return max(a,-a);}
inline void upd(int a,int b,int c,int d,int e){
	if(a>=sr){
		if(a>=kr)return;
		if(a+1<KR)dp[a+1][11][11][b][e|2]=min(dp[a+1][11][11][b][e|2],dp[a][b][c][d][e]);
		else if(a+1==KR)dp[a+1][11][KC][b][e|2]=min(dp[a+1][11][KC][b][e|2],dp[a][b][c][d][e]);
		else{
			for(int y=0;y<W;y++){
				bool d2=false;
				for(int z=min(y,c);z<=max(y,c);z++)if(str[a][z]=='#')d2=true;
				if(str[a+1][y]=='#')d2=true;
				if(a+1==kr&&kc!=y)d2=true;
				if(d2)continue;
				int x=b;
				int ks=0;
				int vt=0;
				for(int z=min(y,c);z<max(y,c);z++){
					bool iL=(min(b,x)<=z)&&(z<=max(b,x));
					bool iR=(min(b,x)<=z+1)&&(z+1<=max(b,x));
					if(!iL&&!iR)ks++;
					else if(!(iL&&iR)){
						if(!vt&&a==SR&&(z==SC||z+1==SC)){vt=1;ks++;}
					//	else if(!vt&&a==sr&&(z==sc||z+1==sc)){vt=1;ks++;}
						else ks+=2;
					}
				}
				if(d!=11&&a>KR&&a<=sr&&min(b,d)<=c&&c<=max(b,d)&&min(b,x)<=c&&c<=max(b,x)){
					if(a-1==SR&&c==SC)ks--;
					else if(a-1==sr&&c==sc)ks--;
					else ks-=2;
				}
				if((SR!=a||y!=SC)&&min(b,x)<=y&&y<=max(b,x))ks+=2;
				else ks++;
				if(d!=11&&a>KR&&a<=sr&&min(b,x)<=c&&c<=max(b,x)&&!(min(b,d)<=c&&c<=max(b,d)))ks++;
				int te=e;
				if(c<min(b,x)||max(b,x)<c)te|=2;
				if(b<min(c,y)||max(c,y)<b)te|=1;
				dp[a+1][11][y][b][te]=min(dp[a+1][11][y][b][te],dp[a][b][c][d][e]+ks);
			}
		}
		return;
	}
	for(int x=0;x<W;x++){
		bool d1=false;
		for(int z=min(x,b);z<=max(x,b);z++)if(str[a][z]=='#')d1=true;
		if(str[a+1][x]=='#')d1=true;
		if(a+1==sr&&sc!=x)d1=true;
		
		if(d1)continue;
		if(a<KR){
			int ks=ABS(x-b)+1;
			if(a+1==KR)dp[a+1][x][KC][b][e|1]=min(dp[a+1][x][KC][b][e|1],dp[a][b][c][d][e]+ks);
			else dp[a+1][x][11][b][e|1]=min(dp[a+1][x][11][b][e|1],dp[a][b][c][d][e]+ks);
			continue;
		}
		if(a>=kr){
			int ks=ABS(x-b)+1;
			if(a==kr&&min(b,x)<=c&&c<=max(b,x))ks++;
			if(d!=11&&a>KR&&min(b,d)<=c&&c<=max(b,d)&&min(b,x)<=c&&c<=max(b,x)){
				if(a-1==SR&&c==SC)ks--;
				else if(a-1==sr&&c==sc)ks--;
				else ks-=2;
			}
			if(d!=11&&a>KR&&min(b,x)<=c&&c<=max(b,x)&&!(min(b,d)<=c&&c<=max(b,d)))ks++;
			int te=e|1;
			if(a==kr&&(c<min(b,x)||max(b,x)<c))te|=2;
			dp[a+1][x][11][b][te]=min(dp[a+1][x][11][b][te],dp[a][b][c][d][e]+ks);
			continue;
		}
		for(int y=0;y<W;y++){
			bool d2=false;
			for(int z=min(y,c);z<=max(y,c);z++)if(str[a][z]=='#')d2=true;
			if(str[a+1][y]=='#')d2=true;
			if(a+1==kr&&kc!=y)d2=true;
			if(a==SR&&a==KR&&min(b,x)<=c&&c<=max(b,x)&&min(c,y)<=b&&b<=max(c,y))continue;
			if(d2)continue;
			int ks=ABS(x-b)+1;
			int vt=0;
			for(int z=min(y,c);z<max(y,c);z++){
				bool iL=(min(b,x)<=z)&&(z<=max(b,x));
				bool iR=(min(b,x)<=z+1)&&(z+1<=max(b,x));
				if(!iL&&!iR)ks++;
				else if(!(iL&&iR)){
					if(!vt&&a==SR&&(z==SC||z+1==SC)){vt=1;ks++;}
			//		else if(!vt&&a==sr&&(z==sc||z+1==sc)){vt=1;ks++;}
					else ks+=2;
				}
			}
			if(d!=11&&a>KR&&min(b,d)<=c&&c<=max(b,d)&&min(b,x)<=c&&c<=max(b,x)){
				if(a-1==SR&&c==SC)ks--;
				else if(a-1==sr&&c==sc)ks--;
				else ks-=2;
			}
			if((SR!=a||y!=SC)&&min(b,x)<=y&&y<=max(b,x))ks+=2;
			else ks++;
			if(d!=11&&a>KR&&min(b,x)<=c&&c<=max(b,x)&&!(min(b,d)<=c&&c<=max(b,d)))ks++;
			int te=e;
			if(c<min(b,x)||max(b,x)<c)te|=2;
			if(b<min(c,y)||max(c,y)<b)te|=1;
		//	if(a==sr)te|=2;
		//	if(a==kr)te|=1;
		//	printf("%d %d %d %d %d -> %d %d %d %d %d: %d\n",a,b,c,d,e,a+1,x,y,b,te,ks);
			dp[a+1][x][y][b][te]=min(dp[a+1][x][y][b][te],dp[a][b][c][d][e]+ks);
		}
	}
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	H=a;W=b;
	for(int i=0;i<a;i++)scanf("%s",str[i]);
	for(int i=0;i<12;i++)for(int j=0;j<12;j++)for(int k=0;k<12;k++)for(int l=0;l<12;l++)
		dp[i][j][k][l][0]=dp[i][j][k][l][1]=dp[i][j][k][l][2]=dp[i][j][k][l][3]=99999999;
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		if(str[i][j]=='s'){sr=i;sc=j;}
		if(str[i][j]=='k'){kr=i;kc=j;}
		if(str[i][j]=='S'){SR=i;SC=j;}
		if(str[i][j]=='K'){KR=i;KC=j;}
	}
	if(SR>KR){
		swap(SR,KR);
		swap(SC,KC);
		swap(sr,kr);
		swap(sc,kc);
	}
	if(SR==KR){
		dp[SR][SC][KC][11][0]=0;
	}else if(SR<KR){
		dp[SR][SC][11][11][1]=0;
	}else{
		dp[SR][SC][11][11][2]=0;
	}
	int ret=99999999;
	for(int i=0;i<a;i++){
		for(int j=0;j<12;j++){
			for(int k=0;k<12;k++){
				for(int l=0;l<12;l++){
					for(int m=0;m<4;m++){
						if(dp[i][j][k][l][m]>999999)continue;
						//printf("%d %d %d %d %d: %d\n",i,j,k,l,m,dp[i][j][k][l][m]);
						int t=0;
						if(j==11)t|=2;
						if(k==11)t|=1;
						if(j<W&&k<W&&k!=j)t|=3;
						if(i>=max(sr,kr)&&(m|t)==3)ret=min(ret,dp[i][j][k][l][m]);
						else upd(i,j,k,l,m);
					}
				}
			}
		}
	}
	if(SR>=sr||KR>=kr)ret=999999999;
	if(ret>999999)printf("CONTRACT\n");
	else printf("%d\n",ret);
}