A picture is stored as a grid of strings: '*' marks a pixel that belongs to some object (a hat, a handbag, a lamp…) and '_' marks background. Objects can touch each other, so two neighbouring '*' pixels are not necessarily part of the same object. The only way to tell is an oracle function:
same_object(p, q) -> bool # p, q are (row, col) of two '*' pixels
Write count_objects(grid: list[str], same_object) -> int that returns how many distinct objects the picture contains.
Guarantees and rules:
- Every object is 4-connected: you can walk between any two of its pixels through up/down/left/right steps that stay inside that object. Diagonal contact never joins pixels.
same_objectis consistent (it answers "do these two pixels carry the same hidden object label?"), but it is expensive: call it only on pairs of'*'pixels that are 4-neighbours, and at most once per such pair. The tests count your calls.- The grid may be empty (
[]) or have empty rows; the answer is then0.
grid = ["**_*",
"**_*",
"____"]
# hidden labels: (0,0),(1,0) are object A; (0,1),(1,1) are object B; (0,3),(1,3) are object C
count_objects(grid, same_object) # 3
Here the 2x2 block on the left is two objects standing side by side, which a plain flood fill over '*' would count as one.
Grids can be up to 400 x 400 pixels. Don't compare every pair of pixels.
Show hint
Do a BFS (or union-find) over the pixels. From a pixel, step to a '*' neighbour only if same_object says they match. To stay within one call per adjacent pair, you can have each pixel ask only about its right and down neighbours and union the matches.