Observations

Restate the problem as minimizing the number of cells that are never painted.

Focusing on a given row, the number of cells painted by one operation is \(0\) or \(2\). That is, if \(W\) is odd, every row necessarily has at least one cell that is never painted.

The same holds for columns.

Solution

Consider cases based on the parities of \(H\) and \(W\).

[1] \(H,W\) = even, even

By painting so as to tile the grid with \(2 \times 2\) squares, all cells can be painted.

[2] \(H,W\) = even, odd (the case “odd, even” is similar)

There will necessarily be at least \(H\) cells that are never painted. By painting in the same way as in the “even, even” case, the number of unpainted cells can be made \(H\).

[3] \(H,W\) = odd, odd

The case \(H=W\)

The number of unpainted cells is at least \(H\). Also, the number of painted cells is a multiple of \(4\), so it is optimal if we can construct a painting in which the number of unpainted cells is at most \(H+3\).

The case \(H=1,3\) is trivial. For \(5 \le H\), by painting as follows, this reduces to the problem with \(H\) smaller by \(4\).

maabbcc.m
.aabbccdd
ll?????dd
ll?????ee
kk?????ee
kk?????ff
jj?????ff
jjiihhgg.
m.iihhggm

The case \(H<W\) (the case \(H>W\) is similar)

By painting the rightmost two columns so as to tile them with \(2 \times 2\) squares, this reduces to the problem with \(W\) smaller by \(2\).

Samples

\(H,W = 4,6\)

aabbcc
aabbcc
ddeeff
ddeeff

\(H,W = 5,6\)

aabbcc
aabbcc
ddeeff
ddeeff
......

\(H,W = 9,11\)

maabbcc.mww
.aabbccddww
llrnn.rddxx
ll.nnooeexx
kkqq.ooeeyy
kkqqpp.ffyy
jjr.pprffzz
jjiihhgg.zz
m.iihhggm..

\(H,W = 9,7\)

iaabb.i
.aabbcc
hhj.jcc
hh...dd
ggj.jdd
ggffee.
i.ffeei
xxyyzz.
xxyyzz.