UOA1158 ICPC: Intelligent Congruent Partition of Chocolate

Problem

卒論のストレス解消に書き殴ってみました。

Source

  • ACM/ICPC Japan Domestic Contest 2008::Problem F

Description

  • 格子状に並んだ0と1で表される図形を1本の折れ線で切断し、連結で合同な(回転・左右反転を許す)2つの図形に分解できるか判定せよ。

Algorithm

  • Backtracking.
    • 図形Aがある(既に占有したものと連結な)1ブロックを占有したら、図形Bも対応する場所の1ブロックを占有する、ということを繰り返す。
      • もちろん対応する場所に0ブロックがあったり、AとBが同じ場所を占有しようとしたら枝刈り。
      • 最初の1つをどれにするかは全通り試す。が、片方は固定してよい。
    • 上記の処理を、図形Bの座標系を8通り(回転x反転)に変えながら試す。

Code

#include <iostream>
#include <algorithm>
#include <cstring>

#define REP(i,e) for(int i=0;i<(int)(e);i++)

using namespace std;

enum{ N=16, L=1<<20, A=2, B=3 };

int v[N][N], li, lj, total;
int AI[4], AJ[4], BI[4], BJ[4];
int ai[N*N], aj[N*N], bi[N*N], bj[N*N];
bool ht[L];

inline int hash(int n){
  static int a[N*N], b[N*N];
  REP(i,n) a[i]=ai[i]*li+aj[i], b[i]=bi[i]*li+bj[i];
  sort(a,a+n); sort(b,b+n);
  int h=0;
  REP(i,n){ h*=10007; h+=a[i]; h=h&(L-1); h*=10007; h+=b[i]; h=h&(L-1); }
  return h;
}

bool backtrack(int l){
  if(total==l){ return true; }
  int h=hash(l); if(ht[h]) return false; ht[h]=true;

  REP(i,l) REP(d,4){
    int nai=ai[i]+AI[d], naj=aj[i]+AJ[d], nbi=bi[i]+BI[d], nbj=bj[i]+BJ[d];
    if(!v[nai][naj] && !v[nbi][nbj] && !(nai==nbi && naj==nbj)){
      v[nai][naj]=A; v[nbi][nbj]=B; ai[l]=nai; aj[l]=naj; bi[l]=nbi; bj[l]=nbj;
      if(backtrack(l+1)) return true;
      v[nai][naj]=0; v[nbi][nbj]=0;
    }
  }

  return false;
}

bool go(){
  memset(ht,false,sizeof ht);  

  REP(i,li) REP(j,lj) if(!v[i][j]){
    v[i][j]=A; ai[0]=i; aj[0]=j;
    REP(ii,li) REP(jj,lj) if(!v[ii][jj]){
      v[ii][jj]=B; bi[0]=ii; bj[0]=jj;
      if(backtrack(1)) return true;
      v[ii][jj]=0;
    }
    v[i][j]=0;
    return false;
  }
  return false;
}

bool compute(){
  AI[0]=-1; AI[1]=0; AI[2]=1; AI[3]=0; AJ[0]=0; AJ[1]=1; AJ[2]=0; AJ[3]=-1;
  BI[0]=-1; BI[1]=0; BI[2]=1; BI[3]=0; BJ[0]=0; BJ[1]=1; BJ[2]=0; BJ[3]=-1;

  REP(a,2){
    REP(d,4){
      if(go()) return true;
      rotate(BI,BI+1,BI+4); rotate(BJ,BJ+1,BJ+4);
    }
    swap(BJ[1],BJ[3]);
  }
  return false;
}

int main(){
  while(cin >> lj >> li && li|lj){
    memset(v,0,sizeof v); total=0;
    REP(i,li) REP(j,lj) cin >> v[i+1][j+1], total+=v[i+1][j+1];
    if(total&1){ cout << "NO" << endl; continue; }
    li+=2; lj+=2; total/=2;
    REP(i,li) REP(j,lj) v[i][j]=(v[i][j] ? 0 : 1);
    cout << (compute() ? "YES" : "NO") << endl;
  }
}

Notes

  • 90分ぐらいで書けた。もっとバグらずに書ければ理想的だけど、まぁこんなものかな。
  • 1ブロックが奇数個のケースなんてあまりにも自明すぎて入ってないだろうと思ったら、ちゃんと入ってたみたいで1回WAりました。
  • コード長は2kBを切った。よく頑張ったと思う。
  • それにしてもスパゲッティだ。