全ての合計 (\(K2^K\)) から\(2^K\) 通りそれぞれについて散らかってないが照らされないマスの合計を引けば、答えになります。散らかってないが照らされないマスの合計を今から求めます。

各散らかっていないマスに対し、そこのマスが照らされないように照明を置く方法の個数を求めて、それを全ての散らかっていないマスに対して合計すれば良いです。

あるマスが照らされないようにするには、そのマスから\(4\)方向に伸びる空きマスとそのマス自身には照明が置かれてはいけませんが、ほかのマスは照明が置かれていてもいなくても問題ありません。よって。そのマスから\(4\)方向に伸びる空きマスとそのマス自身あわせた個数を \(T\) とすると、 \(2^{K-T}\) 通りあります。

あとは、それぞれのマスに対して \(T\) を求められれば良いです。これは \(4\) 方向それぞれに対し、「上 (もしくは下,左,右) 向きに移動したところ、今空きマスが何マス連続している」のような値をそれぞれの向きに対して \(O(HW)\) で計算することで求められます。