题目描述

假设我们有一个由$0$和$1$组成的n×m网格。一条“蛇”是满足以下条件的连通方格序列：
$1.$ 每个蛇的方格中必须是$1$。
$2$. 除序列的第一个和最后一个方格（蛇头和蛇尾）外，每个蛇的方格恰好与另外两个蛇方格在北/南/东/西方向上相邻。

极大蛇是指无法在其任意一端添加一个$1$而不导致以下情况的蛇：
延长蛇的长度，
与其他蛇合并，
违反规则$2$。
以下示例展示了存在或不存在极大蛇的网格（空白方格均为$0$）。注意，第二个网格中不存在极大蛇，因为可以在任意一条蛇的末端添加一个$1$以形成更长的蛇。
对于本题，给定多个网格，需计算每个网格中极大蛇的数量。

输入格式

输入包含多个测试用例。每个测试用例的第一行包含两个正整数$n$和$m$（分别表示网格的行数和列数，最大值均为200）。接下来n行每行包含$m$个字符（$0$或$1$），表示网格内容。最后一个测试用例后接一行$0$ $0$，该输入无需处理。

输出格式

对每个测试用例，输出一行整数，表示网格中极大蛇的数量。

输入示例 1

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

输出示例 1

1  
0  
3  

来源

East Central North America $2006$