## 2013年8月15日

### UVa 387 - A Puzzling Problem

```#include <cstdio>
#include <string>
#include <vector>
#define PB push_back
using namespace std;

struct Piece {
Piece() {}
Piece(int r, int c, const vector<string> & p) : r(r), c(c), p(p) {
size = 0;
for (int h = 0; h < r; h++) {
for (int w = 0; w < c; w++) {
size += (p[h][w] == '1');
}
}
}
int r, c, size;
vector<string> p;
} pieces[10];

int n;
bool solved;

void solve(vector<string> & now, int index, int need) {
if (solved) {
return;
}
if (!need) {
if (index == n) {
solved = true;
for (int r = 0; r < 4; r++) {
printf("%s\n", now[r].c_str());
}
}
return;
}
if (index == n) {
return;
}
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
bool match = true;
vector<string> next(now);
for (int h = 0; h < pieces[index].r && match; h++) {
for (int w = 0; w < pieces[index].c && match; w++) {
if (pieces[index].p[h][w] == '0') {
continue;
}
if (r + h >= 4 || c + w >= 4) {
match = false;
break;
}
match = (now[r + h][c + w] == '0');
next[r + h][c + w] = '1' + index;
}
}
if (match) {
solve(next, index + 1, need - pieces[index].size);
}
}
}
}

int main() {
bool first = true;
while (scanf("%d", &n) && n) {
if (!first) {
puts("");
}
first = false;
for (int i = 0; i < n; i++) {
int r, c;
vector<string> p;
scanf("%d%d", &r, &c);
for (int j = 0; j < r; j++) {
char s[99];
scanf("%s", s);
p.PB(s);
}
pieces[i] = Piece(r, c, p);
}
solved = false;
vector<string> now(4, "0000");
solve(now, 0, 16);
if (!solved) {
puts("No solution possible");
}
}
return 0;
}
```