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