Number of Islands

Time limit1sMemory limit128 MB

Summary
Given a grid of land and sea cells with 8-directional adjacency, count the connected land components.
Level

Easy3 of 10

Topics
Graph, DFS, BFS, Matrix
Solved
No attempts yet

Problem

You are given a map of land and sea made up of square cells. Write a program that counts the number of islands.

From any cell you may walk to a cell that is adjacent horizontally, vertically, or diagonally. In other words, each cell is connected to up to 8 neighboring cells.

Two land cells belong to the same island if there is a path that walks from one to the other while stepping only on land cells. The map is surrounded by sea, and you cannot move outside the map.

Input

The input consists of several test cases. The first line of each test case contains the width ww and the height hh of the map. ww and hh are positive integers not greater than 5050.

The next hh lines describe the map, each line containing ww integers separated by spaces. 11 denotes land and 00 denotes sea.

The last line of the input contains two zeros; this line is not processed.

Output

For each test case, print the number of islands, one per line.

Examples1

  1. Example 1

    Input
    1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0
    Expected output
    0
1
1
3
1
9