TopCoder SRM 651 Div2 Hard FoxConnection4

Div1Mediumを通していると簡単。

問題

H*Wの２次元グリッドが与えられる。
一部のセルは埋められている。

空白セルのうちK個を選択したとき、それらが隣接セル同士で連結しているようなものは何通りあるか。

解法

先にDiv1 Mediumを解いていると簡単。
TopCoder SRM 651 Div1 Medium FoxConnection3 - kmjp's blog

まず連結するKマスの組み合わせを全通り求める。
これはDiv1 Mediumと同様。

あとはそのようなマスの組み合わせが元のH*Wマス中何個あるか列挙すればよい。
最大であるK=8でも連結マスの組み合わせは2725個。

最大で10*10の空白マス中でも合わせて129582個しか条件を満たす連結セル群は存在しない。
10^9+9の剰余なんて不要だったね。

class FoxConnection4 {
	public:
	set<set<pair<int,int> > > S[9];
	int howManyWays(vector <string> board, int k) {
		int i,j,x,y;
		set<pair<int,int> > ts;
		ts.insert(make_pair(0,0));
		S[1].insert(ts);
		
		for(i=1;i<=k-1;i++) {
			ITR(it,S[i]) {
				set<pair<int,int> > s=*it;
				
				ITR(it2,s) {
					int cx=it2->first,cy=it2->second;
					FOR(j,4) {
						int dd[4]={1,0,-1,0};
						int tx=cx+dd[j],ty=cy+dd[j^1];
						if(s.count(make_pair(tx,ty))) continue;
						set<pair<int,int> > s2;
						int dx=(tx<0),dy=(ty<0);
						s2.insert(make_pair(tx+dx,ty+dy));
						ITR(it3,s) s2.insert(make_pair(it3->first+dx,it3->second+dy));
						S[i+1].insert(s2);
					}
				}
				
			}
		}
		
		ll ret=0;
		int H=board.size(), W=board[0].size();
		ITR(it,S[k]) {
			set<pair<int,int> > s=*it;
			int mx=0,my=0;
			ITR(it2,s) mx=max(mx,it2->first+1), my=max(my,it2->second+1);
			FOR(y,H-my+1) FOR(x,W-mx+1) {
				int ok=1;
				ITR(it2,s) if(board[y+it2->second][x+it2->first]=='#') ok=0;
				ret += ok;
			}
		}
		return ret;
	}
}

まとめ

10^9+9という微妙な値の剰余だが、実は不要という問題。