TopCoder

User's AC Ratio

100.0% (11/11)

Submission's AC Ratio

92.9% (13/14)

Tags

Description

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

Input Format

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

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

  • $3 \leq N \leq 500$
  • $2 \leq M \leq 500$
  • $|s_{i}| = M$
  • $s_{i, j} \in \lbrace 0, 1\rbrace$

Output Format

請輸出一行,該行有一個整數,代表有幾個 $3 \times 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