Labelling turns a mask into a table of objects with sizes and positions.
What to build
A program that labels 8-connected regions and reports each one's area, bounding box and centroid.
Requirements
- Number the regions 1, 2, 3, … in the order their first pixel appears in reading order (row by row, left to right). There are at most 9.
- Print the label map: each pixel's label digit, or
.for background. - Then, for each region, print
region K: area A, rows R1-R2, columns C1-C2, centroid (Y, X)with the centroid's mean row Y and mean column X to two decimal places.
Input
Line 1: H and W. Then H rows of # and ..
Output
H map rows, then one line per region.
Constraints
1 ≤ H, W ≤ 40.
Example
Input:
3 4
##..
#..#
...#
Output:
11..
1..2
...2
region 1: area 3, rows 0-1, columns 0-1, centroid (0.33, 0.33)
region 2: area 2, rows 1-2, columns 3-3, centroid (1.50, 3.00)
Why it works
The flood fill gathers each region's pixels, and the area, box and centroid are a count, minimums and maximums, and means over that list.
Examples
Example 1 · Input
3 4 ##.. #..# ...#
Expected output
11.. 1..2 ...2 region 1: area 3, rows 0-1, columns 0-1, centroid (0.33, 0.33) region 2: area 2, rows 1-2, columns 3-3, centroid (1.50, 3.00)
Example 2 · Input
2 3 #.# .#.
Expected output
1.1 .1. region 1: area 3, rows 0-1, columns 0-2, centroid (0.33, 1.00)
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Scan in reading order; when you meet an unlabelled `#`, flood it with the next label and collect its pixels in a list.
Hint 2
The centroid is (sum of rows ÷ area, sum of columns ÷ area).
Solution
Show one correct solution (try it yourself first)
h, w = map(int, input().split())
grid = [input() for _ in range(h)]
labels = [[0] * w for _ in range(h)]
regions = []
for r in range(h):
for c in range(w):
if grid[r][c] == "#" and labels[r][c] == 0:
regions.append([])
k = len(regions)
labels[r][c] = k
stack = [(r, c)]
while stack:
y, x = stack.pop()
regions[-1].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 labels[ny][nx] == 0:
labels[ny][nx] = k
stack.append((ny, nx))
for row in labels:
print("".join(str(v) if v else "." for v in row))
for k, cells in enumerate(regions, 1):
rows = [y for y, x in cells]
cols = [x for y, x in cells]
n = len(cells)
print(f"region {k}: area {n}, rows {min(rows)}-{max(rows)}, columns {min(cols)}-{max(cols)}, centroid ({sum(rows) / n:.2f}, {sum(cols) / n:.2f})")