1691. Distance to the Nearest Marked Square

A grid of r rows and c columns holds 1 for a marked square and 0 for an unmarked one. For every square, print how many moves away its nearest marked square is, as a grid of r lines of c numbers. A move goes up, down, left or right, and no square is blocked.

A marked square prints 0. If the grid holds no 1 at all, every entry is -1.

0 1 0 1 0 1 0 0 0 -> 2 1 2 0 0 0 3 2 3

## The four things that have to be said

directed? no. Every move can be undone. self-loops? there are none: a move always changes square. parallel edges? there are none: two neighbours are joined once each way. unreachable? only in one situation, and it is all or nothing. No square is blocked, so the grid is connected and every square reaches every other; the only way to reach no marked square is for there to BE none, and then the whole grid is -1. A 1 by 1 grid prints 0 if it is marked and -1 if it is not.

## What most people try first

For each unmarked square, a search of its own towards the nearest 1. That is up to r * c searches of r * c squares each, which at the limits is 90000 * 90000 = 8.1 * 10^9 steps.

The next instinct is a formula: for each square, the smallest Manhattan distance to a marked square. That happens to be right HERE, because nothing is blocked, and it is still O(r * c * (number of marks)), and it stops being right the moment a wall is added. The search does not depend on that coincidence.

## Seed every marked square at once

Put EVERY marked square into the queue at distance 0 and run one breadth-first search over the whole grid:

for every square holding 1: dist = 0, push it while the queue is not empty: pop s for each of the four neighbours t of s: if dist[t] is unset: dist[t] = dist[s] + 1, push t

One pass, O(r * c), whatever the marks look like.

## Why the first arrival is the nearest mark

Breadth-first search keeps the queue in non-decreasing order of distance. It starts with every mark at 0, which is non-decreasing, and each push is one more than the value just popped. So the first time a square is reached, no shorter route from any mark exists, and the value written is the distance to the nearest one.

Equivalently, add one artificial vertex joined to every marked square by an edge of length 0 and search from it. Seeding is that construction with the artificial vertex removed, and problem 1686 is the same idea on a plain graph.

## What this is not

Problem 377 also seeds a grid with many sources. It SPREADS a state and prints one number, the minute the last fresh cell changes, with -1 when one never does, and it has blocked cells. This prints the whole distance field, has no blocked cells, and its -1 case is a grid with no marks rather than a cell that cannot be reached.

## Cost

O(r * c) time and memory, 90000 squares at the limits. A distance is at most r + c - 2 = 598, so 32 bit arithmetic is ample.

Constraints - `1 ≤ r ≤ 300` - `1 ≤ c ≤ 300` - Every character is `0` or `1`.