- Each snake square has a 1 in it
- Each snake square touches exactly two other snake squares (north/south/east/west), except the first and last square in the sequence (the head and tail of the snake)

提交: 0 解决: 0

[提交][状态][讨论版][命题人:]

Assume we have an n × m grid of squares, each filled with either 0 or 1. A snake is a connected sequence of grid squares which has the following properties:

- Each snake square has a 1 in it
- Each snake square touches exactly two other snake squares (north/south/east/west), except the first and last square in the sequence (the head and tail of the snake)

Input will consist of multiple test cases. The first line of each test case will contain two positive integers n m indicating the number of rows and columns in the grid (the maximum value of each will be 200). The next n lines will consist of m characters (either '0' or '1') specifying the grid. The last case is followed by a line containing 0 0 which indicates end-of-input and should not be processed.

For each test case, output a single line containing the number of maximal snakes in the grid.

```
7 10
1111111110
0000000010
1100000011
1011110001
1010010001
1010010111
1110011100
7 10
1111111110
0000000010
0001010011
1011010001
1010010001
1010010111
1110011100
7 10
1011111110
0100000010
1101011011
1011010001
1010010001
1010010111
1110011100
0 0
```

```
1
0
3
```