Challenge: Count the Islands

Lab Python Intermediate 20 points

Read a map where # is land and . is water. Land cells that touch up, down, left or right belong to the same island. Print the number of islands and the size (number of cells) of the biggest one.

Input

Line 1: rows cols. Then rows lines of # and ..

Output

Islands: <count>
Biggest: <size>

Biggest is 0 if there is no land.

Example

Input

4 5
##..#
#...#
..#..
.....

Output

Islands: 3
Biggest: 3

Sample input available Sample output available

Editor

Python

Hints

Each unseen # starts a new island.

Flood-fill from it (BFS or DFS) to mark and count the whole island.

Solution explanation

The grid is a graph: cells are vertices and touching cells are edges.

Show solution

from collections import deque
rows, cols = map(int, input().split())
grid = [input().strip() for _ in range(rows)]
seen = [[False] * cols for _ in range(rows)]
count = biggest = 0
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == "#" and not seen[r][c]:
            count += 1
            size = 0
            seen[r][c] = True
            q = deque([(r, c)])
            while q:
                y, x = q.popleft()
                size += 1
                for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
                    if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == "#" and not seen[ny][nx]:
                        seen[ny][nx] = True
                        q.append((ny, nx))
            biggest = max(biggest, size)
print("Islands:", count)
print("Biggest:", biggest)

Output

Answer