当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3316：Snakes on a Plane

题目描述

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)
A maximal snake is one in which we cannot add a 1 to either end without either lengthening the snake, combining two snakes together, or violating rule 2 above. The examples below show grids with and without maximal snakes (all empty squares have 0's in them). Notice that the second grid does not have a maximal snake since you can add a 1 at the end of either snake to get a larger snake.

For this problem, you will be given grids and must count the number of maximal snakes in each.

输入解释

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
该题目是Virtual Judge题目，来自 北京大学POJ
题目来源 East Central North America 2006
源链接： POJ-3316
最后修改于 2020-10-29T06:58:24+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
2000 65536