Loading page…
Practice problem · easy
Kestrel Freight's safety team labels every block of racks on a warehouse floor plan, so a fire marshal can name a block over the radio. The plan is a grid of cells. A # is a rack and a . is an aisle.
Racks that touch side by side belong to the same block, even when the block bends. Racks that only touch at a corner are separate blocks, because a person can walk between them. The team needs the number of labels to print. A floor plan holds up to 400 by 400 cells.
Write count_rack_blocks(floor).
floor is a list of rows, each a string of # (rack) and . (aisle). Every row has the same length.Input: floor = ["##..#", "#...#", "..#..", "....#"]
Output: 4Scan the cells row by row. Each rack cell that no earlier fill has reached starts a new block and a fill.
| Cell scanned | Rack, not yet filled? | Fill marks | Blocks |
|---|---|---|---|
| (0, 0) | yes | (0, 0), (0, 1), (1, 0) | 1 |
| (0, 1) | already filled | 1 | |
| (0, 4) | yes | (0, 4), (1, 4) | 2 |
| (1, 0), (1, 4) | already filled | 2 | |
| (2, 2) | yes | (2, 2) | 3 |
| (3, 4) | yes | (3, 4) | 4 |
(3, 4) is below an aisle at (2, 4), so it does not join the block above it.
Input: floor = ["#.#", ".#.", "#.#"]
Output: 5The five racks touch only at corners, so each one is its own block.
Input: floor = ["...."]
Output: 0A floor with no racks has no blocks.
1 ≤ rows, columns ≤ 400, and every row has the same length# or .The size here is the number of cells: up to 400 × 400 = 160,000. Handling each cell once, with four neighbour checks, is under a million steps.
Starting a fresh search from every rack cell, or sweeping the floor until labels stop changing, can repeat work for every cell of a big block. That is billions of steps on a winding block, so each cell must be handled once.
count_rack_blocks · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.