主唱太拼命了
小方塊喜歡玩方塊遊戲。他有一個 N×M 的表格,每一格都會放著石頭或是木棍,小方塊想要用這個表格合成出越多個石斧越好。令橫列的編號由上到下,而直排為由左到右,同時令第 i 橫列與第 j 個直排交匯處的格子為 (i,j)。小方塊想要計算有幾個 3×2 的子表格是可以合成出石斧的。我們定義一個左上角為 (i,j) 的 3×2 的子表格可以合成出石斧,若滿足以下兩個條件之一:
舉例來說,下圖總共有兩個子表格可以合成出石斧:
給定表格的內容,請幫小方塊計算有幾個 3×2 的子表格可以合成出石斧。
輸入第一行有兩個正整數 N,M,代表表格的大小。
接下來 N 行,第 i 行有一個長度為 M 個字串 si=si,1si,2⋯si,M,若 si,j=0 則代表格子 (i,j) 放的是石頭,否則代表為木棍。
請輸出一行,該行有一個整數,代表有幾個 3×2 子表格可以合成出石斧。
3 4 0000 0110 1110
2
4 4 0000 0100 0110 1110
3