#include #include #include #include using namespace std; typedef vector VS; int rs, cs; VS board; // Is r,c within the bounds of the board? bool valid(int r, int c) { return r >= 0 && r < rs && c >= 0 && c < cs; } // Get the value at r,c or empty if it is out of bounds int get(int r, int c) { if (valid(r,c)) return board[r][c] != '0' ? 1 : 0; else return 0; } // Count the neighbors of r,c int count(int r, int c) { return get(r-1,c) + get(r+1,c) + get(r,c-1) + get(r,c+1); } // Determine if a snake end at r,c can be grown bool cangrow(int r, int c) { return (valid(r-1,c) && get(r-1,c) == 0 && count(r-1,c) == 1) || (valid(r+1,c) && get(r+1,c) == 0 && count(r+1,c) == 1) || (valid(r,c-1) && get(r,c-1) == 0 && count(r,c-1) == 1) || (valid(r,c+1) && get(r,c+1) == 0 && count(r,c+1) == 1); } // Flood-fill from a given r,c replacing f's with t's void flood(int r, int c, char f, char t) { if (valid(r,c) && board[r][c] == f) { board[r][c] = t; flood(r-1,c,f,t); flood(r+1,c,f,t); flood(r,c-1,f,t); flood(r,c+1,f,t); } } int main(void) { while (1) { cin >> rs >> cs; if (rs == 0) break; // Read the board... board.clear(); for (int i = 0; i < rs; ++i) { string s; cin >> s; board.push_back(s); } // For each square in the board... for (int r = 0; r < rs; ++r) { for (int c = 0; c < cs; ++c) { // If the square contains the end of an unmarked snake... if (board[r][c] == '1' && count(r,c) <= 1) { // If the end can be grown... if (cangrow(r,c)) { // Mark the snake (overwrite it with 2's) flood(r, c, '1', '2'); } } } } // All remaining '1' snakes are maximal. int count = 0; // For each square in the board... for (int r = 0; r < rs; ++r) { for (int c = 0; c < cs; ++c) { // If the square contains an unmaked snake... if (board[r][c] == '1') { // Increment the counter count += 1; // and mark the snake (overwrite it with 2's) flood(r, c, '1', '2'); } } } printf("%d\n", count); } return 0; }