AOJ : 0213 - 土地分割 (Subdivide The Land)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0213&lang=jp
日本語なので省略. 長方形のピースを隙間なく敷き詰めるパズルの感覚で解く.

アルゴリズム

再帰によって, 順番に購入者番号ごとに長方形の位置を決定していく.
この際の長方形の置き方はいろいろなパターンがあるが, 置けるパターンであるものは全通り試す.
隙間なく完成できたら, それを解候補とする.

プログラム

#include <iostream>
#include <cstring>
using namespace std;

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

int X,Y,n;
int b[15],k[15],s[10][10];
int sx[15],sy[15],ans[10][10];
bool ansFlg;

//作成された分割法が答えであるかの判定
bool isAns(void){
  rep(i,Y) rep(j,X) if(s[i][j] == 0) return false;
  return true;
}

//[y][x]から[y+h-1][x+w-1]の間の四角形が全て0であるかの判定
bool settable(int y,int x,int h,int w){
  REP(i,y,y+h) REP(j,x,x+w) if(s[i][j]!=0) return false;
  return true;
}

//[y][x]から[y+h-1][x+w-1]の間の四角形にvalを敷き詰める
void setLand(int y,int x,int h,int w,int val){
  REP(i,y,y+h) REP(j,x,x+w) s[i][j] = val;
}

/*
 * 複数答えが見つかってしまったときはtrueを返す
 * それ以外はfalse
 * (ansFlgが答えが存在するかどうかのフラグ)
 */
bool solve(int idx){
  if(idx == -1){
    if(isAns()){
      if(ansFlg) return true;
      ansFlg = true;
      memcpy(ans,s,sizeof(s));
    }
    return false;
  }

  //縦のサイズを決める
  REP(h,1,k[idx]+1){
    if(k[idx] % h != 0) continue;
    int w = k[idx] / h; //横のサイズの決定

    REP(i,sy[idx]-h+1,sy[idx]+1){
      REP(j,sx[idx]-w+1,sx[idx]+1){
        if(i<0 || j<0 || i+h>Y || j+w>X) continue;

        s[sy[idx]][sx[idx]] = 0;
        if(settable(i,j,h,w)){
          setLand(i,j,h,w,idx+1);
          if(solve(idx-1)) return true;
          setLand(i,j,h,w,0);
        }
        s[sy[idx]][sx[idx]] = idx+1;
      }
    }
  }

  return false;
}

int main(void){
  while(cin>>X>>Y>>n && (X||Y||n)){
    rep(i,n) cin>>b[i]>>k[i];
    rep(i,Y) rep(j,X){
      cin>>s[i][j];
      if(s[i][j] != 0){
        sx[s[i][j]-1] = j;
        sy[s[i][j]-1] = i;
      }
    }

    ansFlg = false;

    if(!solve(n-1) && ansFlg){
      rep(i,Y){
        rep(j,X-1) cout<<ans[i][j]<<" ";
        cout<<ans[i][X-1]<<endl;
      }
    }
    else{
      cout<<"NA\n";
    }
  }

  return 0;
}