Computer vision: Count the objects

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: A and 8-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))

Lesson: Connected components and contours →