AOJ 0213 - Subdivide The Land

購入者nを入れる場所を考えるんじゃなくて，(x, y)にどの購入者を入れるか．
つまり，逆に考えるといい．ぴっちり入るという事は(0, 0)から(w-1, h-1)まで入れられれば成功ということ．
重複で入ったものは自然に消えるだろうとか思っちゃいけない(推測)．できちゃうかも．

#include<iostream>

struct P{
	int x, y;
};

int W, H, n;
int memo[16], res[10][10];
P pos[16];

//i番目を置くよー
int rec(int map[10][10], int used, int x, int y){
	if(y == H){//できたよー
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				res[i][j] = map[i][j];
			}
		}
		return 1;
	}

	int res = 0;
	if(map[y][x] != 0){//もう埋まっている
		res += rec(map, used, (x+1)%W, (x+1)%W?y:y+1);
	}

	for(int i=1;i<=n;i++){
		if(used >> i & 1)continue;
		for(int width=1;width<=memo[i];width++){
			if(memo[i] % width != 0)continue;

			int height = memo[i] / width, _map[10][10];
			if(x <= pos[i].x && pos[i].x <= x + width - 1 &&
				 y <= pos[i].y && pos[i].y <= y + height - 1 &&
				 x + width - 1 < W && y + height - 1 < H){
				for(int j=0;j<H;j++){
					for(int k=0;k<W;k++){
						_map[j][k] = map[j][k];
					}
				}

				bool divided = true;
				for(int j=0;j<height&&divided;j++){
					for(int k=0;k<width&&divided;k++){
						if(_map[y+j][x+k] != 0)divided = false;//同じ所に入れない
						_map[y+j][x+k] = i;
					}
				}

				if(!divided)break;

				res += rec(_map, used | (1 << i), (x+width)%W, (x+width)%W?y:y+1);
			}
		}	
	}

	return res;
}

int main(){
	while(std::cin >> W >> H >> n, W){
		for(int i=n;i--;){
			int index;
			std::cin >> index;
			std::cin >> memo[index];
		}

		for(int y=0;y<H;y++){
			for(int x=0;x<W;x++){
				int v;
				std::cin >> v;
				if(v != 0){
					pos[v] = {x, y};
				}
			}
		}

		int map[10][10];
		for(int i=0;i<100;i++){
			map[i/10][i%10] = 0;
		}

		if(rec(map, 0, 0, 0) == 1){
			for(int i=0;i<H;i++){
				std::cout << res[i][0];
				for(int j=1;j<W;j++){
					std::cout << " " << res[i][j];
				}
				std::cout << std::endl;
			}
		}else{
			std::cout << "NA" << std::endl;
		}
	}
}