AOJ 0213 Subdivide the Land
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0213
解法
全探索すればいいらしい。実装キツい。
#include <cstdio> #include <algorithm> using namespace std; typedef pair<int,int> P; const int MAX_N = 15; const int MAX_XY = 10; int N, X, Y; int memo[MAX_N]; int area[MAX_XY][MAX_XY]; int ans[MAX_XY][MAX_XY]; P buyer[MAX_N]; int ans_n; void fill(int x, int y, int w, int h, int n){ for(int i=0; i<w; i++)for(int j=0; j<h; j++) ans[x+i][y+j] = n; } void solve(const int n){ if(n==N){ for(int i=0;i<Y;i++) for(int j=0;j<X;j++) area[j][i] = ans[j][i]; ans_n++; return; } int px = buyer[n].first, py = buyer[n].second; //可能な長方形をすべて試す for(int w=1; w<=memo[n]; w++){ if(memo[n]%w!=0) continue; int h = memo[n]/w; //長方形をずらす for(int dx=0;dx<w;dx++){ for(int dy=0;dy<h;dy++){ //すでにある長方形と重ならないか,はみでないか確認 bool f = true; for(int i=px-dx; i<px-dx+w; i++){ if(i<0 || X<=i){ f=false; break;} for(int j=py-dy; j<py-dy+h; j++){ if(j<0 || Y<=j){ f=false; break; } if(i==px && j==py) continue; if(ans[i][j] != -1){ f=false; break; } } if(!f) break; } if(!f) continue; //塗りつぶす fill(px-dx,py-dy,w,h,n); solve(n+1); fill(px-dx,py-dy,w,h,-1); ans[px][py] = n; } } } } int main(){ while(scanf("%d %d %d", &X,&Y,&N)&&N!=0){ ans_n = 0; for(int i=0;i<MAX_XY;i++)for(int j=0;j<MAX_XY;j++) ans[i][j] = -1; for(int i = 0; i < N; i++){ int b, k; scanf("%d %d", &b, &k); memo[b-1] = k; } for(int y=0;y<Y;y++){ for(int x=0;x<X;x++){ scanf("%d", &area[x][y]); if(area[x][y] != 0){ area[x][y]--; buyer[area[x][y]] = P(x,y); }else{ area[x][y] = -1; } ans[x][y] = area[x][y]; } } solve(0); if(ans_n == 1) for(int i=0;i<Y;i++) for(int j=0;j<X;j++){ printf("%d", area[j][i]+1); if(j==X-1) puts(""); else printf(" "); } else printf("NA\n"); } return 0; }