BookHaven
All DSA problems
MediumGraphsAmazonGoogleMicrosoft

Number of Islands Count

Given a grid of size r × c with 1 = land and 0 = water, count the number of islands. An island is 4-directionally connected land.

**Input**

First line: r c

Next r lines: strings of 0/1 of length c

Examples

Example 1

Input:

4 5
11110
11010
11000
00000

Output: 1

Example 2

Input:

4 5
11000
11000
00100
00011

Output: 3

Constraints

  • 1 ≤ r,c ≤ 50

Target: O(r·c) time · O(r·c) space