tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 2612: Phutball

明らかに問題文に不備があるので、AtCoderから実際にコンテストが行われたときのclarをさがしてきましょう。下の角のマスの隣(下線と同じy座標で盤面の外)はゴールではありません。

#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
char str[31][31];
int dx[]={1,1,1,0,0,-1,-1,-1};
int dy[]={1,0,-1,1,-1,1,0,-1};
map<pair<int,pair<int,int> > ,int> m;
int x[21];
int y[21];
int fi[31][31];
int sz;
int solve(int bit,int row,int col){
	if(row>=18)return 0;
	if(m.count(make_pair(bit,make_pair(row,col))))return m[make_pair(bit,make_pair(row,col))];
	int ret=99999999;
	for(int i=0;i<8;i++){
		int nr=row+dx[i];
		int nc=col+dy[i];
		int tb=bit;
		while(0<=nr&&nr<=18&&0<=nc&&nc<=14){
			if(!~fi[nr][nc]||!(bit&(1<<fi[nr][nc])))break;
			tb-=(1<<(fi[nr][nc]));
			nr+=dx[i];nc+=dy[i];
		}
		if(nr-dx[i]==row&&nc-dy[i]==col)continue;
		if(nr<19&&(nc<0||nc>=15))continue;
		ret=min(ret,solve(tb,nr,nc)+1);
	}
	return m[make_pair(bit,make_pair(row,col))]=ret;
}
int main(){
	for(int i=0;i<19;i++)scanf("%s",str[i]);
	int row=0;
	int col=0;
	for(int i=0;i<31;i++)for(int j=0;j<31;j++)fi[i][j]=-1;
	for(int i=0;i<19;i++)for(int j=0;j<15;j++){
		if(str[i][j]=='O'){row=i;col=j;}
		if(str[i][j]=='X'){
			fi[i][j]=sz;
			x[sz]=i;y[sz]=j;sz++;
		}
	}
	int ret=solve((1<<sz)-1,row,col);
	if(ret>99999)printf("-1\n");
	else printf("%d\n",ret);
}