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