UVa 798 - Tile Puzzle

Tile Puzzle
http://uva.onlinejudge.org/external/7/798.html

問題概要

100*100までのパズルがあたえられる。
10種類までのピースがあたえられる。
何通りでそのパズルを完成させられますか。
ある場所のピースの種類か向きが異なると、違う完成方法と数える。

解法

DFS
100*100*10*2くらい？

ソース

#include<iostream>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)

using namespace std;

const int N = 100;

bool used[N][N];
int W, H, remain[10], cnt, n, w[10], h[10];

bool canPut(int y, int x, int id){
  if(y + h[id] > H || x + w[id] > W){
    return false;
  }
  REP(i, y, y+h[id]){
    REP(j, x, x+w[id]){
      if(used[i][j])return false;
    }
  }
  return true;
}

void put(int y, int x, int id, bool v){
  REP(i, y, y+h[id]){
    REP(j, x, x+w[id]){
      used[i][j] = v;
    }
  }
}

void dfs(int y, int x){
  if(x == W){
    y++;
    x=0;
  }
  if(y == H){
    cnt++;
    return;
  }
  if(used[y][x]){
    dfs(y, x+1);
    return;
  }
  rep(id, n){
    if(remain[id] == 0)continue;
    rep(d, 2){
      bool flag = canPut(y, x, id);
      if(flag){
        put(y, x, id, true);
        remain[id]--;
        dfs(y, x+1);
        remain[id]++;
        put(y, x, id, false);
      }
      if(w[id] == h[id])break;
      swap(w[id], h[id]);
    }
  }
}

void init(){
  rep(i, H){
    rep(j, W){
      used[i][j] = false;
    }
  }
  cnt = 0;
}
int main(){
  while(cin >> W >> H >> n){
    if(W == 0)break;
    init();
    rep(i, n)cin >> remain[i] >> w[i] >> h[i];
    dfs(0, 0);
    cout << cnt << endl;
  }
  return 0;
}