SRM 428 Div1 Hard SpecificPolyominoCovering

問題概要

以下のような二つの図形がある。

A  A
AAAA

BB

これらを回転させずに与えられた平面に敷き詰めたい。
平面は'.'が図形を置いてはいけないマスで、'X'が図形を必ず置かなければならないマスである。

敷き詰め方が複数通りある場合は辞書順で最小のものを求めよ。

制約条件

平面の幅,高さ≦50

方針

まずは敷き詰めが可能かどうかを調べることについて考える。左上から順に頂点を見ていき、今見ている頂点へ図形を置く方法を場合分けして考える。

. 今見ている頂点が置けないマス
どうやっても置けない。

XX Bが置ける

X??X Aが置ける
XXXX

A,Bが共に置けるとき、Bを置いてしまっても自由度が下がることはない。
よってAしか置けないときのみAを置けばよい。

全て見終わった後に置けてないマスがあればどうやっても置けないことがわかる。
次に辞書順で最小にすることを考える。
Aは、Aしか置けないところにしか置いていない（そこにAを置かないと置き方が作れない）ので、上の置き方で

B  B
BBBB

となっているところ（のうちAに置き換えられる場所）をgreedyにAに置き換えれば辞書順で最小になる。
ちょうど図形の切れ目になっているBしか置き換えられないことに注意する。

ソースコード

bool align(vector<string> r,int y,int x){
  int k=0;
  while(x>=0&&r[y][x]=='B')x--, k++;
  return k%2==1;
}

class SpecificPolyominoCovering {
  public:
  vector <string> findCovering(vector <string> r) {

    int h=r.size(), w=r[0].size();
    rep(i,h)rep(j,w-1){
      if(r[i][j]!='X')continue;
      if(r[i][j]=='X'&&r[i][j+1]=='X'){
        r[i][j]=r[i][j+1]='B';
        continue;
      }
      if(j>w-4||i==h-1)continue;
      if(r[i][j]=='X'&&r[i+1][j]=='X'&&r[i+1][j+1]=='X'&&r[i+1][j+2]=='X'&&r[i+1][j+3]=='X'&&r[i][j+3]=='X')
        r[i][j]='A',r[i+1][j]='A',r[i+1][j+1]='A',r[i+1][j+2]='A',r[i+1][j+3]='A',r[i][j+3]='A';
    }

    rep(i,h)cerr<<r[i]<<endl;

    rep(i,h)rep(j,w)if(r[i][j]=='X')return vector<string>();
    
    rep(i,h-1)rep(j,w-3)
      if(r[i][j]=='B'&&r[i+1][j]=='B'&&r[i+1][j+1]=='B'&&r[i+1][j+2]=='B'&&r[i+1][j+3]=='B'&&r[i][j+3]=='B')
        if(align(r,i,j)&&align(r,i+1,j)&&!((r[i][j+1]!='B')^(r[i][j+2]!='B')))
        r[i][j]='A',r[i+1][j]='A',r[i+1][j+1]='A',r[i+1][j+2]='A',r[i+1][j+3]='A',r[i][j+3]='A';

    rep(i,h)cerr<<r[i]<<endl;

    return r;
  }
};