PKU : 1020 - Anniversary Cake

問題概要

http://poj.org/problem?id=1020

正方形の形をしたs*sのケーキを, a1*a1, a2*a2,...,an*an のN個のケーキに分割できるかどうかを答えてください.

アルゴリズム

深さ優先探索で枝刈です.
各深さにおいては, N個の正方形の内, どれで切り取っていくかを決定します.
切り取る位置は, 左上からループで見ていって, 一番最初に見つかった切り取れる場所で切り取ります.

プログラム

int s,n;
int t[20];
bool flg[100][100],used[20];

//[y][x]〜[y+len-1][x+len-1]のケーキを切り取れるかどうかの判定
bool check(int x,int y,int len){
  if(x + len > s || y + len > s) return false;

  REP(i,y,y+len){
    REP(j,x,x+len){
      if(flg[i][j]){
        return false;
      }
    }
  }
  return true;
}

//[y][x]〜[y+len][x+len]にvalを書き込む
void draw(int x,int y,int len,bool val){
  REP(i,y,y+len){
    REP(j,x,x+len){
      flg[i][j] = val;
    }
  }
}

//ケーキ切り取りDFS
//戻り値：true-全て切り取れる, false-切り取れない
//rem：あといくつ切り取らないといけないか
bool dfs(int rem){
  if(rem == 0) return true;

  //左上から見ていって, 空いている場所を探す(ここが切り取る位置になる)
  int sx,sy;
  for(sx=0;sx<s;sx++){
    for(sy=0;sy<s;sy++){
      if(!flg[sy][sx]){
        break;
      }
    }
    if(sy != s) break;
  }

  int before = -1;
  rep(i,n){
    //すでに切り取った or すでに探索した値 or (sx,sy)からti*tiは無理
    if(used[i] || before == t[i] || !check(sx,sy,t[i])) continue;

    //書き込み
    draw(sx,sy,t[i],true);
    used[i] = true;
    if(dfs(rem-1)) return true;
    used[i] = false;
    draw(sx,sy,t[i],false);

    before = t[i];
  }

  return false;
}

int main(){
  int T;
  scanf("%d",&T);

  while(T--){
    scanf("%d%d",&s,&n);

    int sum = 0;
    rep(i,n){
      scanf("%d",&t[i]);
      sum += t[i] * t[i];
    }
    if(sum != s*s){
      printf("HUTUTU!\n");
      continue;
    }

    sort(t,t+n,greater<int>());
    memset(flg,0,sizeof(flg));
    memset(used,0,sizeof(used));
    bool ans = dfs(n);
    printf("%s\n", ans ? "KHOOOOB!" : "HUTUTU!");
  }
}