No.018 C

中心が $(y, x)$ の菱型の中にある黒マスの個数を $B(y, x)$ として, $B(y+1, x)$ および $B(y, x+1)$ を $B(y, x)$ をもとに求める.

これはずらしたときの差分を足し引きすればいい. 斜め方向の累積和をあらかじめ計算しておくことで, $O(1)$ で計算できる.

最後に $B(y, x) = 0$ となる個数を数える.