Codeforces Round #44 (Div 2) C. Crossword

問題概要

6つの英大文字からなる単語が与えられる。
これらを使って下のようなクロスワードパズルを作る。

NOD
BAA
YARD
AIRWAY
NEWTON
BURN

BAA...
U.I...
R.R...
NEWTON
..A..O
..YARD

パズルは単語によってちょうど4つの長方形に分割されていなければならない。
このとき、パズルで辞書順で最も最初に来るものを求めよ。
存在しないならば"Impossible"を出力せよ。

解法

問題文からは読み取りにくいが、縦に並ぶ単語が3つ、横に並ぶ単語が3つで、
サンプルのように単語と単語の交点が7つ（両端で交わるのが6つ、途中で交わるのが1つ）
あるようなクロスワードを作ればよいようである。

したがって、単語の位置をnext_permutationなどで6!通り全部試して、クロスワードになっているか判定してやればよい。

ソースコード

string in[6];
vs tmp,ans;

bool ok(int *l){
  if(l[0]!=l[1]+l[2]-1||l[3]!=l[4]+l[5]-1)return 0;
  return 1;
}
bool ck(char *h,char *t){
  if(h[1]!=h[4]||t[4]!=h[0]||t[1]!=h[3])return 0;
  if(t[3]!=h[2]||t[0]!=h[5]||t[2]!=t[5])return 0;
  return 1;
}

void run()
{
  ans.clear();
  int l[6]; char h[6],t[6];
  rep(i,6)getline(cin,in[i]);
  sort(in,in+6);
  do{
    rep(i,6){
      l[i]=in[i].size();
      h[i]=in[i][0]; t[i]=in[i][l[i]-1];
    }
    if(!ok(l)||!ck(h,t)||in[0][l[1]-1]!=in[3][l[4]-1])continue;
    tmp=vs(l[0],string(l[3],'.'));

    rep(i,l[0])tmp[i][l[4]-1]=in[0][i];
    rep(i,l[1])tmp[i][0]=in[1][i];
    rep(i,l[2])tmp[l[0]-l[2]+i][l[3]-1]=in[2][i];
    rep(i,l[3])tmp[l[1]-1][i]=in[3][i];
    rep(i,l[4])tmp[0][i]=in[4][i];
    rep(i,l[5])tmp[l[0]-1][l[3]-l[5]+i]=in[5][i];

    if(ans.empty()||tmp<ans)ans=tmp;
  }while(next_permutation(in,in+6));
 
  if(ans.empty())cout<<"Impossible"<<endl;
  else rep(i,ans.size())cout<<ans[i]<<endl;
}