After thresholding, a mask still holds noise. Drop the small objects and describe the outlines of the rest.
What to build
A program that removes small 8-connected objects and reports each remaining object's area, boundary length and fill ratio.
Requirements
- Find the 8-connected objects, ordered by their first pixel in reading order. Keep those with area at least A; the others become background.
- Print the cleaned map:
#for boundary pixels of kept objects (a side neighbour is background or outside the image),ofor their interior pixels and.elsewhere. - Then print
kept K of N objectsand, for each kept object in order,object i: area A, boundary B, fill F, where F is area ÷ bounding-box area with two decimal places.
Input
Line 1: H, W and the minimum area A. Then H rows of # and ..
Output
H map rows, the kept line and one line per kept object.
Constraints
1 ≤ H, W ≤ 40; A ≥ 1.
Example
Input:
4 5 2
###..
###.#
###..
.....
Output:
###..
#o#..
###..
.....
kept 1 of 2 objects
object 1: area 9, boundary 8, fill 1.00
Why it works
Area filtering removes specks that are smaller than any real object, and a pixel with a background neighbour on a side lies on the object's outline, so counting those pixels measures the outline's length.
Examples
4 5 2 ###.. ###.# ###.. .....
###.. #o#.. ###.. ..... kept 1 of 2 objects object 1: area 9, boundary 8, fill 1.00
3 3 1 #.. .#. ..#
#.. .#. ..# kept 1 of 1 objects object 1: area 3, boundary 3, fill 0.33
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
First collect every 8-connected object as a list of pixels, in reading order of their first pixel, then keep the lists with at least the minimum area.
Hint 2
A pixel is interior when all four side neighbours are inside the image and `#`; otherwise it is a boundary pixel.
Solution
Show one correct solution (try it yourself first)
h, w, min_area = map(int, input().split())
grid = [input() for _ in range(h)]
seen = [[False] * w for _ in range(h)]
objects = []
for r in range(h):
for c in range(w):
if grid[r][c] == "#" and not seen[r][c]:
seen[r][c] = True
stack, cells = [(r, c)], []
while stack:
y, x = stack.pop()
cells.append((y, x))
for dy in (-1, 0, 1):
for dx in (-1, 0, 1):
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))
objects.append(cells)
kept = [cells for cells in objects if len(cells) >= min_area]
def on(y, x):
return 0 <= y < h and 0 <= x < w and grid[y][x] == "#"
out = [["."] * w for _ in range(h)]
report = []
for i, cells in enumerate(kept, 1):
edge = 0
for y, x in cells:
if on(y - 1, x) and on(y + 1, x) and on(y, x - 1) and on(y, x + 1):
out[y][x] = "o"
else:
out[y][x] = "#"
edge += 1
rows = [y for y, x in cells]
cols = [x for y, x in cells]
box = (max(rows) - min(rows) + 1) * (max(cols) - min(cols) + 1)
report.append(f"object {i}: area {len(cells)}, boundary {edge}, fill {len(cells) / box:.2f}")
for row in out:
print("".join(row))
print(f"kept {len(kept)} of {len(objects)} objects")
for line in report:
print(line)