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); }