A grid of 0s (water) and 1s (land) is given. An island is a group of 1s connected horizontally or vertically (not diagonally). Count the islands.
Line 1: two integers r and c (rows and columns).
The next r lines each contain a string of c characters, each 0 or 1.
The number of islands.
Example 1
3 3 110 010 001
2
The top-left L-shape is one island; the lone 1 at the corner is another → 2.
Example 2
1 1 1
1
A single land cell.
Example 3
2 2 00 00
0
All water — no islands.
Scan the grid; when you find a 1 you have not visited yet, you have found a new island.
From that cell, flood-fill (BFS or DFS) to every connected 1 and mark them visited so you count the island only once.
Iterate every cell; on an unvisited 1, increment the count and flood-fill (BFS) all 4-directionally connected land, marking it visited.
import sys
from collections import deque
data = [l for l in sys.stdin.read().split('\n')]
r, c = map(int, data[0].split())
grid = [data[1 + i] for i in range(r)]
seen = [[False] * c for _ in range(r)]
islands = 0
for i in range(r):
for j in range(c):
if grid[i][j] == '1' and not seen[i][j]:
islands += 1
q = deque([(i, j)])
seen[i][j] = True
while q:
x, y = q.popleft()
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < r and 0 <= ny < c and grid[nx][ny] == '1' and not seen[nx][ny]:
seen[nx][ny] = True
q.append((nx, ny))
print(islands)
Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.