remaked mine sweeper

●STEP1
制約式の「H×Wは３で割り切れない」より
H×W≡1,2(mod3) ⇔H≡1,2(mod3),W≡1,2(mod3)と同値変形可能です。

●STEP2
まず一次元の場合の解法を考えてみましょう。
以下のような問題を考えてみます。
「$A_{j}$=$B_{j-1}$+$B_{j}$+$B_{j+1}$である長さWの配列Aが与えられる。Bの値を求めよ」

STEP1よりW≡1,2なので余りが１の場合、２の場合に場合分けして考えてみます。
①Wの余りが1の時
全てのマスは３回ずつ選ばれるのでAを合計して、3で割った商を求めることでAの合計を求めることが可能です。
調べたいマスをj番目とすると$B_{(j+2)％W}$,$B_{(j+5)％W}$.....$B_{(j+W-2)％W}$を合計から引くことで$B_{j}$を求めることが出来ます。
②Wの余りが2の時
余りが１の時と同様に爆弾の個数の合計を求めることが出来ます。
調べたいマスをj番目とすると$B_{(j+1)％W}$,$B_{(j+4)％W}$.....$B_{(j+W-1)％W}$の和から答えの合計を引くことで$B_{j}$の答えを求めることが出来ます。
①、②は左右の累積和を用いることにより前処理O(W),それぞれO(1)で実装可能です。

●STEP3
STEP2の問題を２次元に拡張します。
i行目(1<=i<=H)についてSTEP2を考えることで$B_{(i-1)％H,j}$+$B_{i,j}$+$B_{(i+1)％H,j}$が全てのj(1<=j<=W)について求まります。
次にj行目についてSTEP2を考えることによって全ての$B_{i,j}$を求めることが出来ます。
全体の計算量はO(HW)となります。