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