Searching from the answer backward

Key idea

The expensive question

Some grid problems ask, for every cell, whether it can reach some destination. Running a search from each cell answers it and costs a full traversal per cell.

The trick is that reachability questions can usually be turned around. Instead of asking which cells can reach the edge, ask which cells the edge can reach, searching backward along the same connections.

One search from the destinations answers the question for every cell at once.

Why it works

Reverse the movement rule too

If moving forward requires going downhill, then searching backward requires going uphill. The rule inverts along with the direction.

Getting that inversion wrong produces a search that runs and returns confidently wrong answers, which is much harder to spot than a crash. Write the forward rule down, then write its reverse explicitly, before coding.

On a real cell the two rules pick out different neighbors, and seeing them side by side is the cheapest way to confirm you have inverted it rather than copied it.

Key idea

Two destinations means two searches

When cells must reach both of two destinations, run one search per destination and intersect the results. Each search is linear, so two of them are still linear.

Trying to answer both in one traversal is possible with two flags per cell and is fiddlier for no gain. Two sets and an intersection is clearer and the same complexity.

Key idea

The same idea for marking what to keep

A related shape: some regions are protected because they touch the border and the rest are not. Rather than testing each region for border contact, search from the border and mark everything it reaches as protected.

Then a single sweep converts everything unmarked. Two passes, both linear, and no per-region bookkeeping at all. Recognizing that this is the same reversal as the reachability version is the point.