$N \leq M,0 \leq K \leq \frac{NM}{2}$ として一般性を失わないので、以下はこれが成り立つとします。
$K = 0,1$ の時、 損失 はどのように塗っても $0$ です。
$\left( N,M,K \right)= \left( 2,2,2 \right)$ の時、 損失 はどのように塗っても $1$ です。また $K=2$ かつ $\left( N,M \right) = \left( 2,2 \right)$ でない場合は左上の角と右下の角を塗ればよいです。
$K \geq 3$ の場合を考えます。

一度黒色で塗るマスの個数の条件を無視して、 損失 が $0$ となるような塗り方を考えます。マス目の左上方向から右下方向へ引いた $N+M-1$ 本の斜め線を考えると以下のような塗り方はしても構いません。

• $2$ 本以上の連続する斜め線を選び、選択した斜め線上のマスを黒く塗る。

ここで斜め線が通るマスの数は左下から順に $1,2, \cdots , N-1 , N , N , \cdots , N ,N , N-1 , N-2 , \cdots , 1$ のようになります。また、 $N$ は $M-N+1$ 個連続しています。
よってこの数列の長さ $2$ 以上の区間を選択し区間の総和が $K$ となるものを選択できればよいですが、そのような区間がない場合もあるかもしれないので微調整する方法を考えます。

数列 $A$ を斜め線が通るマスの数 $A = \left( 1,2, \cdots , N-1 , N , N , \cdots , N ,N , N-1 , N-2 , \cdots , 1 \right)$ として $A_1 + A_2 + \cdots + A_{\mathrm{id}} \geq \frac{NM}{2}$ となる最小の $\mathrm{id}$ を取ります。
このとき、 $\mathrm{id}+3$ 番目以降の斜め線が通る部分をどう塗るかは $\mathrm{id}$ 番目以前の斜め線が通る部分をどう塗るかと独立に考えられます。イメージとしてはマス目を左下の部分と右上の部分に分割します。
ここで $\mathrm{id}+3$ 番目以降の斜め線が通る部分に属し、かつ右上のマスから左に偶数マス、下に偶数マス進んだマスは黒く塗ってもよく、この条件を満たすマスは互いに影響を及ぼしません。よってそのようなマスの数だけ黒いマスを追加で塗ることができます。

そのようなマスの数 $S$ が $N-1$ 以上とします。 $A_1 + A_2 + \cdots + A_{\mathrm{id'}} \leq K$ となる最大の $\mathrm{id'}$ を取ったとき、 $K - \left( A_1 + A_2 + \cdots + A_{\mathrm{id'}} \right) < A_{\mathrm{id'}+1} \leq N$ なので $K - \left( A_1 + A_2 + \cdots + A_{\mathrm{id'}} \right) \leq S$ 個のマスを右上で黒く塗ることができます。
ここで $S$ は $\mathrm{id}+3 \leq i \leq N+M-1$ である偶数 $i$ について $\lfloor \frac{A_i+1}{2} \rfloor$ を足し合わせた値です。 $N=M$ の時 $\lfloor \frac{N-2}{2} \rfloor = X$ として $S = \frac{X \left( X+1 \right)}{2}$ でありこれは $N \geq 10$ において $N-1$ 以上になり、 $N$ が固定されたとき $M$ が増えるほど $S$ は大きくなっていきます。
よって $S < N-1$ となる $\left( N,M \right)$ は有限であり、 $A_1$ から $A_{\mathrm{id}}$ の中の長さ $2$ 以上の区間の総和と $0$ 以上 $S$ 以下の数を足し合わせて $K$ ができないケースは特に $\left( N,M,K \right)= \left( 3,3,4 \right)$ のみです。

\(\left( N,M,K \right)= \left( 3,3,4 \right)\) は以下のようにすれば 損失 が \(0\) となります。

101
000
101

以上より \(\left( N,M,K \right)= \left( 2,2,2 \right)\) 以外は 損失 を \(0\) とできます。