Given a m by n square grids. Suppose that each square is either land of water. An example is a follows, which shows a 4 by 5 grid with land squares filled with green and water squares filled with blue.

Two land squares are considered in the same island if there are adjacent. In the above example, the grids has 3 different islands. Note that diagonal pairs of lands are not considered adjacent. Describe an algorithm to output the number of islands of a given m by n square grid. The running time of your algorithm should be O(mn). You may assume that the input is an m by n array. A[i,j] = 1 means that square [i,j] is land, and A[i,j] = 0 means that square [i,j] is water. Thus the above grid is given as:

Hint: Consider a graph with every land square as a vertex, and there is an edge connects every pair of adjacent lands. What are islands in this graph?

1-0-0-0 0 1-0-0-0