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

沒有留言:

張貼留言