Codeforces 26 C. Parquet

問題

nxmマスの長方形を、
1x2のタイルa枚
2x1のタイルb枚
2x2のタイルc枚を使って隙間なく埋めたい。
（使わないタイルがあってもよいが、タイルを回転させたり、重ねてはならない）

それが可能なら、タイルの敷き詰め方を一通り出力せよ。
タイルの1マスはアルファベット1文字によりあらわされ、辺で隣接するタイルは違うアルファベットをもつものとする。
不可能ならIMPOSSIBLEを出力せよ。

制約条件

n,m≦100

方針

n,mが両方奇数ならば不可能。
片方が奇数のときは1x2の長方形を使ってまず一辺を埋め、残りを偶数×偶数の長方形にする。
偶数の長方形にしたら、greedyにタイルを敷いていけばいい。

途中でタイルが足りなくなったらIMPOSSIBLEである。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int n,m,a,b,c;
char ans[100][101];
void put(int y1,int x1,int y2,int x2){
  bool use[26]={};
  int y[]={y1,y2},x[]={x1,x2};
  rep(p,2)rep(q,2)rep(d,4){
    int ny=y[p]+dy[d],nx=x[q]+dx[d];
    if(0<=ny&&ny<n&&0<=nx&&nx<m&&isalpha(ans[ny][nx]))
      use[ans[ny][nx]-'a']=1;
  }
  rep(i,26)if(!use[i]){
    for(int y=y1;y<=y2;y++)for(int x=x1;x<=x2;x++)
      ans[y][x]='a'+i;
    return;
  }
}
bool solve(){
  if(n%2&&m%2)return 0;
  int h=n, w=m;
  if(n%2){
    rep(i,m/2){
      if(--a<0)return 0;
      put(n-1,i*2,n-1,i*2+1);
    }
    h--;
  }
  if(m%2){
    rep(i,n/2){
      if(--b<0)return 0;
      put(i*2,m-1,i*2+1,m-1);
    }
    w--;
  }
  rep(i,h/2)rep(j,w/2){
    if(a>1){
      put(i*2,j*2,i*2,j*2+1);
      put(i*2+1,j*2,i*2+1,j*2+1);
      a-=2;
    }
    else if(b>1){
      put(i*2,j*2,i*2+1,j*2);
      put(i*2,j*2+1,i*2+1,j*2+1);
      b-=2;
    }
    else if(c){
      put(i*2,j*2,i*2+1,j*2+1);
      c--;
    }
    else return 0;
  }
  return 1;
}
void run(){
  cin>>n>>m>>a>>b>>c;
  memset(ans,0,sizeof(ans));
  if(solve()){
    rep(i,n)cout<<ans[i]<<endl;
  }
  else cout<<"IMPOSSIBLE"<<endl;
}