FunctionRacerProblemsRace

Blocks to the Nearest Shop

MediumGraphsPython, JavaScript, TypeScript, Java, C++

town is a rectangular map given as a list of strings of equal length. Each character is 'S' for a shop, '.' for a street cell or '#' for a building. A walk moves up, down, left or right, one cell at a time, through street cells and shop cells only; buildings block the way.

Return a grid of integers with the same shape as town: for a street cell, the fewest moves needed to walk from it to any shop; 0 for a shop cell; and -1 for a building or for a street cell from which no shop can be reached.

Example 1

town ["S.#","...","#.S"]
returns [[0,1,-1],[1,2,1],[-1,1,0]]

The two shops are at the corners; the centre cell is two moves from either shop; the buildings get -1.

Example 2

town [".#S",".#."]
returns [[-1,-1,0],[-1,-1,1]]

The left column is walled off from the shop by buildings, so its cells get -1.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems