Counting objects is one of the most common questions asked of a mask, and the answer depends on connectivity.
What to build
A program that counts connected objects with 4-connectivity and with 8-connectivity.
Requirements
- Foreground pixels are
#. With 4-connectivity, neighbours share a side; with 8-connectivity, diagonal pixels are neighbours too. - Print
4-connected: Aand8-connected: B.
Input
Line 1: H and W. Then H rows of # and ..
Output
Two lines.
Constraints
1 ≤ H, W ≤ 80.
Example
Input:
3 4
#..#
....
#..#
Output:
4-connected: 4
8-connected: 4
Why it works
Each flood fill visits exactly one whole component, so the number of floods started during the scan is the number of objects.
Examples
Example 1 · Input
3 4 #..# .... #..#
Expected output
4-connected: 4 8-connected: 4
Example 2 · Input
3 3 #.# .#. #.#
Expected output
4-connected: 5 8-connected: 1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Write one flood-fill counter that takes a list of neighbour offsets, and call it twice.
Hint 2
Mark a pixel as seen when you push it onto the stack, not when you pop it.
Solution
Show one correct solution (try it yourself first)
h, w = map(int, input().split())
grid = [input() for _ in range(h)]
FOUR = [(-1, 0), (1, 0), (0, -1), (0, 1)]
EIGHT = FOUR + [(-1, -1), (-1, 1), (1, -1), (1, 1)]
def count(steps):
seen = [[False] * w for _ in range(h)]
n = 0
for r in range(h):
for c in range(w):
if grid[r][c] == "#" and not seen[r][c]:
n += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
y, x = stack.pop()
for dy, dx in steps:
ny, nx = y + dy, x + dx
if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] == "#" and not seen[ny][nx]:
seen[ny][nx] = True
stack.append((ny, nx))
return n
print("4-connected:", count(FOUR))
print("8-connected:", count(EIGHT))