AOJ0213 土地分割

たぶん2013年最後の更新。

解法

---

DFSにパターン数を足したような再帰すると良い。
枝狩りは、『面積 % 高さ != 0』のときと『すでに誰かの土地がある』とこらへん。
なんかうまく全探できなかったので修行が必要かも。あんまり変数をグローバル化しすぎると良くないね(確信)
計算量が怪しかったが普通に良かった。

ソース

---

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
#define fr first
#define sc second
typedef pair < int , int > Pi;
typedef pair < int , Pi > Pii;
  
int h, w, n, ans[10][10];
vector< Pii > memo;
  
int wy, wx;
void plus_n( int y, int x, int nt){
  wy = y;
  wx = ( x + nt ) % w;
  if(!wx) wy++;
  return ;
}
 
int dfs( const int mas[][10], const int used, const int y, const int x){
  if( y == h){ //exit
    memcpy( ans, mas, sizeof(int)*100);
    return 1;
  }
  int ret = 0;
  if( mas[y][x] != 0){
    plus_n( y, x, 1);
    ret += dfs( mas, used, wy, wx);
  }else{
    for(int bit = 0 ; bit < n ; bit++ ){
      if( (used >> bit) & 1 ) continue; // もうやってある
  
      for(int i = 1 ; i <= memo[bit].fr ; i++ ){ //高さ決定
        if( memo[bit].fr % i != 0 ) continue; // 長方形無理
        int height = i, width = memo[bit].fr / i;
  
        if( y <= memo[bit].sc.fr && y > memo[bit].sc.fr - height &&
            x <= memo[bit].sc.sc && x > memo[bit].sc.sc - width &&
            y + height - 1 < h && x + width - 1 < w){
          int java[10][10];
          bool ok = true;
          memcpy( java, mas, sizeof(int)*100);
          for(int j = 0 ; j < height ; j++ ){
            for(int k = 0 ; k < width ; k++ ){
              if(java[j + y][k + x]) ok = false;
              java[j + y][k + x] = bit + 1;
            }
          }
          if(ok){
            plus_n( y, x, width);
            ret += dfs( java, used|(1<<bit), wy, wx);
          }
        }
      }
    }
  }
  return ret;
}
int main(){
  while(cin >> w >> h >> n , w){
    memo.resize( n);
    for(int i = 0, bf ; i < n ; i++ ){
      cin >> bf;
      cin >> memo[bf - 1].fr;
    }
    for(int i = 0, c ; i < h ; i++ ){
      for(int j = 0 ; j < w ; j++ ){
        cin >> c;
        if(c)memo[c - 1].sc = Pi( i, j);
      }
    }
    int mas[10][10] = {{}};
    if(dfs( mas, 0, 0, 0) == 1){
      for(int i = 0 ; i < h ; i++ ){
        for(int j = 0 ; j < w ; j++ ){
          cout << ( j ? " " : "" ) << ans[i][j];
        }
        cout << endl;
      }
    }else cout << "NA" << endl;
  }
}