LC: Walls and Gates - spiralgo/algorithms GitHub Wiki

Walls and Gates

The Essence:

If the grid is simultaneously being traversed starting from the gates in every direction, each first-arrival in an empty gate would be its short distance. Then a traversal simultaneously starting from all the gates would bring the right result.

Details:

The procedure described above can be implemented using BFS and is in fact inspired by this algorithm. This shows how having prerequisite knowledge in some problem-solving field can contribute creation of solution ideas.