範例程式碼 uva798
//uva798
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 15
#define W 105
using namespace std;
int w[N], h[N], m[N], n, ans;
bool puz[W][W];
bool valid(int nx, int ny, int nw, int nh) {
if(nx+nw > w[0] || ny+nh > h[0]) return false;
static int dx, dy;
for(dx = nx; dx < nx + nw; ++dx)
for(dy = ny; dy < ny + nh; ++dy)
if(puz[dx][dy])
return false;
return true;
}
void setTile(int nx, int ny, int nw, int nh, bool val) {
static int dx, dy;
nw += nx;
nh += ny;
for(dx = nx ; dx < nw; ++dx)
for(dy = ny ; dy < nh; ++dy)
puz[dx][dy] = val;
}
void pmap(void) {
static int x, y;
for(x = 0; x < w[0]; ++x) {
for(y = 0; y < h[0]; ++y)
putchar(puz[x][y] ? 'X':'_');
putchar('\n');
}
putchar('\n');
}
void dfs(int nx, int ny) {
if(ny == h[0]) {
if(nx == w[0] - 1) {
++ans;
return;
}
else {
++nx;
ny = 0;
}
}
int i;
if(!puz[nx][ny]) {
for(i = 1; i <= n; ++i) {
if(m[i]) {
if(valid(nx, ny, w[i], h[i])) {
setTile(nx, ny, w[i], h[i], true); --m[i];
dfs(nx, ny + 1);
setTile(nx, ny, w[i], h[i], false); ++m[i];
}
if(w[i] != h[i] && valid(nx, ny, h[i], w[i])) {
setTile(nx, ny, h[i], w[i], true); --m[i];
dfs(nx, ny + 1);
setTile(nx, ny, h[i], w[i], false); ++m[i];
}
}
}
}
else
dfs(nx, ny+1);
}
int main(void) {
int i;
while(scanf("%d%d%d", &w[0], &h[0], &n) == 3) {
// input
for(i = 1; i <= n; ++i)
scanf("%d%d%d", &m[i], &w[i], &h[i]);
// initialize
ans = 0;
memset(puz, false, sizeof(puz));
// solve
dfs(0, 0);
// output
printf("%d\n", ans);
}
return 0;
}