The answer is the total squares (\(K2^K\)) subtracted by the sum of the numbers of unlightened tidy squares for each \(2^K\) ways. We will now find the sum of the numbers of unlightened tidy squares.

For each tidy square, we will find the number of ways of placing lamps so that the square will not be lightened, and then sum them up for all tidy square.

When a square is not lightened, the lamps should not be placed in the square itself and the empty squares in the four directions, but it does not matter whether lamps are placed in the other squares. Therefore, let \(T\) be the number of empty squares in the four directions and the square it self, then there are \(2^{K-T}\) ways to achieve it.

All that left is to find \(T\) for each square. This can be found in \(O(HW)\) time by, for each of the four directions, calculating “the number of consecutive empty squares above (or below, in the left or right)”.