AOJ : 0213 - 土地分割 (Subdivide The Land)
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0213&lang=jp
日本語なので省略. 長方形のピースを隙間なく敷き詰めるパズルの感覚で解く.
アルゴリズム
再帰によって, 順番に購入者番号ごとに長方形の位置を決定していく.
この際の長方形の置き方はいろいろなパターンがあるが, 置けるパターンであるものは全通り試す.
隙間なく完成できたら, それを解候補とする.
プログラム
#include <iostream> #include <cstring> using namespace std; #define REP(i,n,m) for(int i=n;i<m;i++) #define rep(i,n) REP(i,0,n) int X,Y,n; int b[15],k[15],s[10][10]; int sx[15],sy[15],ans[10][10]; bool ansFlg; //作成された分割法が答えであるかの判定 bool isAns(void){ rep(i,Y) rep(j,X) if(s[i][j] == 0) return false; return true; } //[y][x]から[y+h-1][x+w-1]の間の四角形が全て0であるかの判定 bool settable(int y,int x,int h,int w){ REP(i,y,y+h) REP(j,x,x+w) if(s[i][j]!=0) return false; return true; } //[y][x]から[y+h-1][x+w-1]の間の四角形にvalを敷き詰める void setLand(int y,int x,int h,int w,int val){ REP(i,y,y+h) REP(j,x,x+w) s[i][j] = val; } /* * 複数答えが見つかってしまったときはtrueを返す * それ以外はfalse * (ansFlgが答えが存在するかどうかのフラグ) */ bool solve(int idx){ if(idx == -1){ if(isAns()){ if(ansFlg) return true; ansFlg = true; memcpy(ans,s,sizeof(s)); } return false; } //縦のサイズを決める REP(h,1,k[idx]+1){ if(k[idx] % h != 0) continue; int w = k[idx] / h; //横のサイズの決定 REP(i,sy[idx]-h+1,sy[idx]+1){ REP(j,sx[idx]-w+1,sx[idx]+1){ if(i<0 || j<0 || i+h>Y || j+w>X) continue; s[sy[idx]][sx[idx]] = 0; if(settable(i,j,h,w)){ setLand(i,j,h,w,idx+1); if(solve(idx-1)) return true; setLand(i,j,h,w,0); } s[sy[idx]][sx[idx]] = idx+1; } } } return false; } int main(void){ while(cin>>X>>Y>>n && (X||Y||n)){ rep(i,n) cin>>b[i]>>k[i]; rep(i,Y) rep(j,X){ cin>>s[i][j]; if(s[i][j] != 0){ sx[s[i][j]-1] = j; sy[s[i][j]-1] = i; } } ansFlg = false; if(!solve(n-1) && ansFlg){ rep(i,Y){ rep(j,X-1) cout<<ans[i][j]<<" "; cout<<ans[i][X-1]<<endl; } } else{ cout<<"NA\n"; } } return 0; }