AOJ 1303: Hobby on Rails
長い間AOJからは離れていたのですが、気が向いたので解きました。
探索して盤面をつくり、後はたどるだけで頑張ればよいです。何でこれで探索パートが一瞬で実行できるのかはよくわかっていません。
座標を上手く持つ方法が強いて言えば難しいくらい?
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; char in[2]; char t[8][8]; int conv[8][8]; int H,W; int ret; int used[20][20]; int pr[8]; int pc[8]; int pd[8]; int lr[4][3]={{1,1,0},{0,2,1},{1,1,2},{2,0,1}}; int lc[4][3]={{0,2,1},{1,1,2},{2,0,1},{1,1,0}}; int rr[4][3]={{1,1,2},{0,2,1},{1,1,0},{2,0,1}}; int rc[4][3]={{0,2,1},{1,1,0},{2,0,1},{1,1,2}}; int at[8][3]; int au[8][3]; int al[8][3]; int ps; int v[8][3][1<<6]; void go(int a,int b){ for(int i=0;i<ps;i++)for(int j=0;j<3;j++)for(int k=0;k<(1<<ps);k++)v[i][j][k]=-1; int len=0; int A=a; int B=b; int bit=0; while(1){ v[A][B][bit]=len; len+=al[A][B]+1; int ta=at[A][B];int tb=au[A][B]; A=ta; if(tb==0){ if(bit&(1<<A))B=1; else B=2; bit^=(1<<A); }else B=0; if(~v[A][B][bit])break; } ret=max(ret,len-v[A][B][bit]); } void calc(){ /*for(int i=0;i<ps;i++){ for(int j=0;j<3;j++){ printf("(%d, %d, %d)",at[i][j],au[i][j],al[i][j]); } printf("\n"); } printf("\n");*/ for(int i=0;i<ps;i++)for(int j=0;j<3;j++){ go(i,j); } } void dfs_route(int P1,int P2,int TR,int TC,int MR,int MC,int L){ if(MR<0||MC<0||MR>=H||MC>=W)return; if(~conv[MR][MC]){ int M=conv[MR][MC]; bool ok=false; for(int i=0;i<3;i++){ if(!~at[M][i]&&((t[MR][MC]=='L'&&TR==MR*2+lr[pd[M]][i]&&TC==MC*2+lc[pd[M]][i])||(t[MR][MC]=='R'&&TR==MR*2+rr[pd[M]][i]&&TC==MC*2+rc[pd[M]][i]))){ at[P1][P2]=M;au[P1][P2]=i; at[M][i]=P1;au[M][i]=P2; al[P1][P2]=al[M][i]=L; ok=true;break; } } if(!ok)return; for(int i=0;i<ps;i++){ for(int j=0;j<3;j++){ if(!~at[i][j]){ int sr=pr[i]*2; int sc=pc[i]*2; int kr=pr[i];int kc=pc[i]; if(t[pr[i]][pc[i]]=='L'){sr+=lr[pd[i]][j];sc+=lc[pd[i]][j]; if(lr[pd[i]][j]==0)kr--;if(lr[pd[i]][j]==2)kr++; if(lc[pd[i]][j]==0)kc--;if(lc[pd[i]][j]==2)kc++;} if(t[pr[i]][pc[i]]=='R'){sr+=rr[pd[i]][j];sc+=rc[pd[i]][j]; if(rr[pd[i]][j]==0)kr--;if(rr[pd[i]][j]==2)kr++; if(rc[pd[i]][j]==0)kc--;if(rc[pd[i]][j]==2)kc++;} dfs_route(i,j,sr,sc,kr,kc,0); at[at[P1][P2]][au[P1][P2]]=au[at[P1][P2]][au[P1][P2]]=-1; at[P1][P2]=au[P1][P2]=-1; return; } } } calc(); at[at[P1][P2]][au[P1][P2]]=au[at[P1][P2]][au[P1][P2]]=-1; at[P1][P2]=au[P1][P2]=-1; return; } if(used[MR][MC])return; used[MR][MC]=1; if(t[MR][MC]=='S'){ int nr,nc,mr,mc; if(TR%2){ nr=TR;nc=MC*4+2-TC; mr=MR;mc=(nc-MC-1); }else{ nc=TC;nr=MR*4+2-TR; mc=MC;mr=(nr-MR-1); } dfs_route(P1,P2,nr,nc,mr,mc,L+1); }else{ if(TR%2){ dfs_route(P1,P2,MR*2,MC*2+1,MR-1,MC,L+1); dfs_route(P1,P2,MR*2+2,MC*2+1,MR+1,MC,L+1); }else{ dfs_route(P1,P2,MR*2+1,MC*2,MR,MC-1,L+1); dfs_route(P1,P2,MR*2+1,MC*2+2,MR,MC+1,L+1); } } used[MR][MC]=0; } void dfs_dir(int a){ if(a==ps){ for(int i=0;i<ps;i++)for(int j=0;j<3;j++){ at[i][j]=au[i][j]=-1; } for(int i=0;i<H;i++)for(int j=0;j<W;j++)used[i][j]=0; int sr=pr[0]*2; int sc=pc[0]*2; int kr=pr[0];int kc=pc[0]; if(t[pr[0]][pc[0]]=='L'){sr+=lr[pd[0]][0];sc+=lc[pd[0]][0]; if(lr[pd[0]][0]==0)kr--;if(lr[pd[0]][0]==2)kr++; if(lc[pd[0]][0]==0)kc--;if(lc[pd[0]][0]==2)kc++;} if(t[pr[0]][pc[0]]=='R'){sr+=rr[pd[0]][0];sc+=rc[pd[0]][0]; if(rr[pd[0]][0]==0)kr--;if(rr[pd[0]][0]==2)kr++; if(rc[pd[0]][0]==0)kc--;if(rc[pd[0]][0]==2)kc++;} dfs_route(0,0,sr,sc,kr,kc,0); return; } for(int i=0;i<4;i++){ pd[a]=i; dfs_dir(a+1); } } int main(){ int a,b; while(scanf("%d%d",&b,&a),a){ H=a;W=b; for(int i=0;i<a;i++)for(int j=0;j<b;j++){ scanf("%s",in); t[i][j]=in[0]; } for(int i=0;i<a;i++)for(int j=0;j<b;j++)conv[i][j]=-1; ret=0; ps=0; for(int i=0;i<a;i++)for(int j=0;j<b;j++){ if(t[i][j]=='L'||t[i][j]=='R'){ conv[i][j]=ps; pr[ps]=i;pc[ps++]=j; } } if(ps%2){ printf("0\n");continue; } dfs_dir(0); printf("%d\n",ret); } }