Walls and Gates Problem

Walls and Gates Problem — ExecCode Hard DSA Practice

Solve the Walls and Gates problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Description Problem You are given a 2D grid representing a map of rooms, gates, and walls. Each cell contains one of the following integer values: 0 represents a gate. -1 represents a wall or obstacle. 2147483647 (INTMAX) represents an empty room. Fill each empty room with the distance to its nearest gate. If a room cannot reach any gate, leave it as 2147483647. Distances are measured in Manhattan steps (up, down, left, right) and only travel through empty rooms (you cannot pass through walls). Input Format The input is provided on stdin as follows: - First line: two integers r and c, the number of rows and columns. Next r lines: each line contains c integers separated by spaces describing the grid. Example stdin blob for a 2x2 grid: 2 2 2147483647 0 2147483647 2147483647 Output Format Print the transformed grid with the same dimensions. Each output line corresponds to a row; values are separated by a single space. Empty rooms that can reach a gate must be replaced by the shortest distance (non-negative integer). Walls (-1) and gates (0) remain unchanged. Constraints 1 <= r, c <= 1000 (tests fit in memory/time limits typical for multi-source BFS) - Use Manhattan steps (up/down/lef…

Examples

Input raw = "2 2\n2147483647 0\n2147483647 2147483647"; Output "1 0\n2 1". Input raw = "3 3\n0 2147483647 2147483647\n2147483647 2147483647 2147483647\n2147483647 2147483647 0"; Output "0 1 2\n1 2 1\n2 1 0". Input raw = "4 4\n2147483647 -1 0 2147483647\n2147483647 2147483647 2147483647 -1\n2147483647 -1 2147483647 -1\n0 -1 2147483647 2147483647"; Output "3 -1 0 1\n2 2 1 -1\n1 -1 2 -1\n0 -1 3 4"

Constraints

1<=N<=10^5

Practice Walls and Gates free on ExecCode. Browse DSA problems, topic map, and placement guides.