PKU 2961 Sylvester construction

http://poj.org/problem?id=2961
再帰的に定義されている行列のある範囲の数字を出力するというような問題。

再帰する。
長方形の重なり判定を少し考えさせられた。

int out[30][30];
ll x,y,sx,sy;

bool in(ll ux,ll uy,ll si){
  return
    !(x+sx<=ux || ux+si<=x ||
      y+sy<=uy || uy+si<=y);
}

void dfs(ll ux,ll uy,ll si,int mi){
  if(si==1){
    out[ux-x][uy-y]=mi?-1:1;
    return;
  }
  if(in(ux,uy,si/2))dfs(ux,uy,si/2,mi);
  if(in(ux+si/2,uy,si/2))dfs(ux+si/2,uy,si/2,mi);
  if(in(ux,uy+si/2,si/2))dfs(ux,uy+si/2,si/2,mi);
  if(in(ux+si/2,uy+si/2,si/2))dfs(ux+si/2,uy+si/2,si/2,!mi);
}

main(){
  int t;
  cin>>t;
  while(t--){
    ll si;
    cin>>si>>y>>x>>sy>>sx;
    memset(out,0,sizeof(out));
    dfs(0,0,si,0);
    rep(i,sx){
      rep(j,sy)cout<<out[i][j]<<' ';
      cout<<endl;
    }
    cout<<endl;
  }
}