TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (17/17)

Submission's AC Ratio

95.2% (20/21)

Tags

Description

小方塊喜歡玩方塊遊戲。他有一個 N×M 的表格,每一格都會放著石頭或是木棍,小方塊想要用這個表格合成出越多個石斧越好。令橫列的編號由上到下,而直排為由左到右,同時令第 i 橫列與第 j 個直排交匯處的格子為 (i,j)。小方塊想要計算有幾個 3×2 的子表格是可以合成出石斧的。我們定義一個左上角為 (i,j)3×2 的子表格可以合成出石斧,若滿足以下兩個條件之一:

  • (i,j),(i+1,j),(i,j+1) 格子放著石頭,(i+1,j+1),(i+2,j+1) 放著木棍。
  • (i,j),(i,j+1),(i+1,j+1) 格子放著石頭,(i+1,j),(i+2,j) 放著木棍。

舉例來說,下圖總共有兩個子表格可以合成出石斧:

給定表格的內容,請幫小方塊計算有幾個 3×2 的子表格可以合成出石斧。

Input Format

輸入第一行有兩個正整數 N,M,代表表格的大小。

接下來 N 行,第 i 行有一個長度為 M 個字串 si=si,1si,2si,M,若 si,j=0 則代表格子 (i,j) 放的是石頭,否則代表為木棍。

  • 3N500
  • 2M500
  • |si|=M
  • si,j{0,1}

Output Format

請輸出一行,該行有一個整數,代表有幾個 3×2 子表格可以合成出石斧。

Sample Input 1

3 4
0000
0110
1110

Sample Output 1

2

Sample Input 2

4 4
0000
0100
0110
1110

Sample Output 2

3

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~8 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2