PKU 1099 Square Ice
http://poj.org/problem?id=1099
水分子の結合を矛盾なく出力しろというような問題。
dfsしました。
適当に上から決め打ちしたらWAもらいました。
int n; char out[100][100]; bool dfs(int nu){ if(nu==n*n)return true; int cx=nu/n,cy=nu%n; if(out[cx*4+1][cy*4+3]=='O') return dfs(nu+1); out[cx*4+1][cy*4+3]='O'; rep(l,4){ int k=l+2&3; int k2=l+3&3; int x=cx*4+1+2*dx[k],y=cy*4+3+2*dy[k]; int x2=cx*4+1+2*dx[k2],y2=cy*4+3+2*dy[k2]; if(min(x,y)<=0 || x>=n*4-1)continue; if(min(x2,y2)<=0 || x2>=n*4-1)continue; if(out[x][y]=='H')continue; if(out[x2][y2]=='H')continue; out[x][y]=out[x2][y2]='H'; out[x-dx[k]][y-dy[k]]=k&1?'|':'-'; out[x2-dx[k2]][y2-dy[k2]]=k2&1?'|':'-'; if(dfs(nu+1))return true; out[x][y]=out[x2][y2]=' '; out[x-dx[k]][y-dy[k]]=' '; out[x2-dx[k2]][y2-dy[k2]]=' '; } out[cx*4+1][cy*4+3]=' '; return false; } void solve(){ memset(out,' ',sizeof(out)); rep(i,n)rep(j,n){ int t; cin>>t; if(!t)continue; out[i*4+1][j*4+3]='O'; if(t==-1){ out[i*4-1][j*4+3]=out[i*4+3][j*4+3]='H'; out[i*4][j*4+3]=out[i*4+2][j*4+3]='|'; }else{ out[i*4+1][j*4+2]=out[i*4+1][j*4+4]='-'; out[i*4+1][j*4+1]=out[i*4+1][j*4+5]='H'; } } dfs(0); rep(i,n*4+2){ out[i][0]=out[i][n*4+2]='*'; out[i][n*4+3]=0; out[0][i]='*'; out[n*4-2][i]='*'; } out[n*4-1][0]=0; rep(i,n*4)cout<<out[i]<<endl; } main(){ int ca=0; while(cin>>n,n){ printf("Case %d:\n\n",++ca); solve(); } }