Codeforces 86 B. Tetris revisited

問題

nxmのグリッドがある。
グリッドの一部のマスは障害物'#'で埋められている。

それ以外のマスを、ブロック2個〜ブロック5個の塊(縦または横につながったもの。形は自由)で埋めることができるか。
できるなら埋め方の一例を出力し、そうでない場合は-1を出力せよ。

制約条件

n,m≦1000

方針

1x2のブロックまたは2x1のブロックを最初に置けるだけ置き、
残った隙間を1x2のブロックと同じ色のブロックで置くようにしたら通った。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int h,w;
string in[1000];
void put(int y1,int x1,int y2,int x2){
  bool use[10]={};
  rep(d,4){
    int y=y1+dy[d], x=x1+dx[d];
    if(y<0||x<0||y>=h||x>=w||!isdigit(in[y][x]))continue;
    use[in[y][x]-'0']=1;
  }
  rep(d,4){
    int y=y2+dy[d], x=x2+dx[d];
    if(y<0||x<0||y>=h||x>=w||!isdigit(in[y][x]))continue;
    use[in[y][x]-'0']=1;
  }
  rep(i,10)if(!use[(y1+x1*3+i)%10]){
    in[y1][x1]=in[y2][x2]='0'+(y1+x1*3+i)%10;
    break;
  }
}
int get(int y,int x,int c,bool paint){
  if(paint)in[y][x]='0'+c;
  else in[y][x]='-';
  rep(d,4){
    int ny=y+dy[d],nx=x+dx[d];
    if(ny<0||nx<0||ny>=h||nx>=w)continue;
    if(!paint&&isdigit(in[ny][nx]))c=in[ny][nx]-'0';
    if(paint&&in[ny][nx]=='-'||!paint&&in[ny][nx]=='.')get(ny,nx,c,paint);
  }
  return c;
}
void run(){
  cin>>h>>w;
  rep(i,h)cin>>in[i];
  rep(i,h)rep(j,w){
    if(j<w-1&&in[i][j]=='.'&&in[i][j+1]=='.')put(i,j,i,j+1);
    if(i<h-1&&in[i][j]=='.'&&in[i+1][j]=='.')put(i,j,i+1,j);
  }
  rep(i,h)rep(j,w)if(in[i][j]=='.'){
    int c=get(i,j,-1,0);
    if(c<0){
      cout<<-1<<endl;
      return;
    }
    get(i,j,c,1);
  }
  rep(i,h)cout<<in[i]<<endl;
}