問題概要
長さ $w$ で ., # の $2$ 種の文字からなる長さ $h$ の文字列の配列 $\mathcal S = \langle S_1, S_2, \dots, S_h \rangle$ が与えられる．
配列中の文字を # から . に変える操作を何回か行うことで # のみからなる $2 \times 2$ の部分が存在しないようにするためには，最小で何回の操作が必要か？
……という問題を $t$ 回解け．
制約
- $1 \leq t \leq 100$
- $2 \leq h \leq 7$
- $2 \leq w \leq 7$
準備
説明の都合上，以降 $\mathcal S$ 及び各 $\mathcal S_i$ の添字を $0$-indexed に読み替えます．
解法
$( i, j ) \in \mathbb \{ 0, 1, \dots, h - 1\} \times \{ 0, 1, \dots, w - 1 \}$ の昇順*1に元々が # であるような $\mathcal S_{ i, j }$ を . に書き換えるか否かを両方試す全探索を考えます．計算時間が十分であればこの方法で解を得られますが，全ての $\mathcal S_{ i, j }$ が # だったりするとパッと分かる上界が $O( 2^{ hw } )$ 時間になってしまってまずいので，高速化する方法を考えます．
ある $i, j$ ($0 < i, j$) に対して $\mathcal S_{ i, j }$ が # のとき，$\mathcal S_{ i, j }$ を # のままにできるか否かは，$\mathcal S_{ i, j - 1 }, \mathcal S_{ i - 1, j }, \mathcal S_{ i - 1 , j - 1 }$ のどれかを . にしたか否かと同値です．それ以前の選択は今および以降に影響しないので，$w - 1$ 文字前までの文字をどうしたかが一致している状態から先での最適な選択は同じになります．よって，そのような状態の内それまでの操作回数が最小なもののみ考慮すればよいです．
直前 $w + 1$ 文字の選択の履歴は，
- $i$ 文字前を
#にしたなら下から $i$ ビット目 ($0$-Indexed) が $1$ - $i$ 文字前を
.にしたなら下から $i$ ビット目が $0$
であるような整数（＝ビット列）としてエンコードできます．これを踏まえると，次のように状態をとる動的計画法を考えることができます：
\[
\mathit{ dp }[i][j][s] := \text{$iw + j$ 文字目まで決め終わって，直前 $w + 1$ 文字の履歴が $s$}
\]
ただ，このままだと $( i, j )$ の「次」の計算が面倒なので，
\[
\mathit{ ind }( i, j ) = iw + j
\]
として
\[
\mathit{ dp }[ \mathit{ ind }( i, j ) ][s] := \text{$\mathit{ ind }( i, j )$ 文字目まで決め終わって，直前 $w + 1$ 文字の履歴が $s$}
\]
とします．遷移の説明のためにいくつかの記号を導入します：
- $m = 2^{ w + 1 } - 1$ とする．
- bitwise and を表す二項演算を $\otimes$ とする．
- bitwise or を表す二項演算を $\oplus$ とする．
- $a \overset \min \leftarrow b$ を $a \leftarrow \min( a, b )$ とする．
で，$\mathit{ dp }[ \mathit{ ind }( i, j ) ][s]$ からの遷移は，
- 文字 $\mathcal S_{ i,j }$ を
.にする：
\[
\mathit{ dp }[ \mathit{ ind }( i, j ) + 1 ][ 2s \otimes m ] \overset \min \leftarrow \mathit{ dp }[ \mathit{ ind }( i, j ) ][s] + \begin{cases}
0 & \text{(if $\mathcal S_{ i, j } = \text{'.'}$) }\\
1 & \text{(if $\mathcal S_{ i, j } = \text{'#'}$) }
\end{cases}
\]
- $0 < i \land 0 < j \land ( s \otimes 2^0 = 0 \lor s \otimes 2^{ w - 1 } = 0 \lor s \otimes 2^w = 0 )$ のとき，文字 $\mathcal S_{ i, j }$ を
#にする：
\[
\mathit{ dp }[ \mathit{ ind }( i, j ) + 1 ][ 2s \otimes m \oplus 1 ] \overset \min \leftarrow \mathit{ dp }[ \mathit{ ind }( i, j ) ][s]
\]
となります．これだと元々 . だった文字を # に変更する操作を許容してしまっていますが，それによって解が改善されることは無いので誤答にはならず，記述量を削減できます．
この DP の状態数は $\Theta( hw2^w )$ 個で各状態からの遷移は定数個です．よって，$1$ ケースあたり $\Theta( hw2^w )$ 時間，全体では $\Theta( thw2^w )$ 時間となります．
コード
constexpr auto INF = LIM<>::max() / 2; int solve() { IN( int, H, W ); VS board( H ); cin >> board; const auto index = [&]( const int i, const int j ) { return i * W + j; }; const int mask = ( 1 << ( W + 1 ) ) - 1; static int dp[ 64 ][ 1 << 8 ]; // dp[ # of considerd ][ history of last W ] := min cost fill( AALL( dp ), INF ); dp[0][0] = 0; REP( i, H ) { REP( j, W ) { REP( s, 1 << ( W + 1 ) ) { chmin( dp[ index( i, j ) + 1 ][ ( s << 1 ) & mask ], dp[ index( i, j ) ][s] + ( board[i][j] == '#' ) ); if ( !i || !j || !( ( s & 1 ) && ( s & 1 << ( W - 1 ) ) && ( s & 1 << W ) ) ) { chmin( dp[ index( i, j ) + 1 ][ ( s << 1 | 1 ) & mask ], dp[ index( i, j ) ][s] ); } } } } return *min_element( ALL( dp[ H * W ] ) ); } int main() { IN( int, T ); REP( T ) { cout << solve() << LF; } cout << flush; return 0; }
*1:順序対を列として見たときの辞書式順序での昇順．
