In a grid of 1 (land) and 0 (water), an island is a group of land cells joined up, down, left or right. Count the islands.
Input
The first line has r and c (1 ≤ r, c ≤ 300). Each of the next r lines has c characters, each 0 or 1.
Output
The number of islands.
Examples
Example 1 · Input
4 5 11110 11010 11000 00000
Expected output
1
Example 2 · Input
4 5 11000 11000 00100 00011
Expected output
3
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Scan every cell; at an unvisited '1', count an island and flood it.
Hint 2
Flood with a stack (or queue) of cells, marking each one as you push it.
Hint 3
Neighbours are up, down, left and right only.
Solution
Show one correct solution (try it yourself first)
r, c = map(int, input().split())
grid = [input() for _ 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
seen[i][j] = True
stack = [(i, j)]
while stack:
y, x = stack.pop()
for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
if 0 <= ny < r and 0 <= nx < c and grid[ny][nx] == "1" and not seen[ny][nx]:
seen[ny][nx] = True
stack.append((ny, nx))
print(islands)