Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Walls and Gates

Medium
graphbfsmatrix

You are given a grid where -1 is a wall, 0 is a gate, and 2147483647 (INF) is an empty room. Fill each empty room with the distance to its nearest gate (leave INF if unreachable). Return the grid.

Input

  • Line 1: r c
  • Next r lines: the grid rows

Output: the filled grid, one row per line.

Example 1
Input:
4 4
2147483647 -1 0 2147483647
2147483647 2147483647 2147483647 -1
2147483647 -1 2147483647 -1
0 -1 2147483647 2147483647
Output:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
Example 2
Input:
1 2
-1 0
Output:
-1 0

Constraints

  • 1 ≤ r, c ≤ 250
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.