AtCoder Beginner Contest 173, C : H and V

問題文

　https://atcoder.jp/contests/abc173/tasks/abc173_c

問題概要

　$H \times W$ のグリッド状の盤面があって，$i$ 行目 $j$ 列は白または黒で塗られている．
　この盤面からいくつかの行およびいくつかの列を選び，選んだ行・列のセルを全て赤く塗ることを考える．このとき，操作後の盤面で黒いセルがちょうど $K$ 個になるような行・列の選び方の総数を求めよ．

制約

• $1 \leq H, W \leq 6$
• $1 \leq K \leq HW$

解法

　制約を見てみると，盤面のサイズがかなり小さいです．このサイズならば，行・列の選び方を全て試したとしても高々 $2^6 \times 2^6 = 2^{ 12 }$ 通りしかないので，全て試すことができます．行・列の部分集合を整数にマッピングしてその整数を全通り試すテクニック（いわゆる bit 全探索）をすれば，問題を解くことができます．
　計算量は，それぞれの選び方について盤面を走査して黒いセルを数える部分で bit 全探索とは別に $\Theta( HW )$ 時間がかかるので，$\Theta( 2^{ H + W } HW )$ 時間となります．

コード

int main()
{
	IN( int, H, W, K );
	VS board( H );
	cin >> board;

	int res = 0;
	REP( s, 1 << H )
	{
		REP( t, 1 << W )
		{
			int cnt = 0;
			REP( i, H )
			{
				REP( j, W )
				{
					if ( ( s & 1 << i ) || ( t & 1 << j) )
					{
						continue;
					}
					cnt += board[i][j] == '#';
				}
			}
			res += cnt == K;
		}
	}

	cout << res << endl;

	return 0;
}