小方塊喜歡玩方塊遊戲。他有一個 $N \times M$ 的表格,每一格都會放著石頭或是木棍,小方塊想要用這個表格合成出越多個石斧越好。令橫列的編號由上到下,而直排為由左到右,同時令第 $i$ 橫列與第 $j$ 個直排交匯處的格子為 $(i, j)$。小方塊想要計算有幾個 $3 \times 2$ 的子表格是可以合成出石斧的。我們定義一個左上角為 $(i, j)$ 的 $3 \times 2$ 的子表格可以合成出石斧,若滿足以下兩個條件之一:
舉例來說,下圖總共有兩個子表格可以合成出石斧:
給定表格的內容,請幫小方塊計算有幾個 $3 \times 2$ 的子表格可以合成出石斧。
輸入第一行有兩個正整數 $N, M$,代表表格的大小。
接下來 $N$ 行,第 $i$ 行有一個長度為 $M$ 個字串 $s_i=s_{i,1}s_{i,2}\cdots s_{i,M}$,若 $s_{i, j} = 0$ 則代表格子 $(i, j)$ 放的是石頭,否則代表為木棍。
請輸出一行,該行有一個整數,代表有幾個 $3 \times 2$ 子表格可以合成出石斧。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~8 | 無額外限制 | 100 |