← 返回 doordash 的题目列表Multi-Source BFS: Nearest Source for Each Cell in a Grid
类型：online_judge
Problem: Distance to the Nearest Source in a 2D Grid (Multi-Source BFS)
Given an m x n grid grid where:
grid[i][j] = 0 denotes a source cell;
grid[i][j] = -1 denotes an obstacle cell that cannot be traversed;
grid[i][j] = 1 denotes a normal traversable cell.
Compute, for every cell, the shortest Manhattan distance to the nearest source cell (0). You may move 4-directionally (up/down/left/right), each move costing 1.
Source cells have distance 0.
Obstacle cells should remain -1 in the output.
Any traversable cell that cannot reach any source should be -1.
Return/print an m x n distance matrix dist.
Input (stdin)
First line: two integers m n.
Next m lines: n integers each, the grid.
Output (stdout)
Print m lines, each with n integers: the distance matrix.
Constraints
1 <= m, n <= 1000
Target time complexity close to O(m*n)
Example
Input:
3 4
1 1 1 0
1 -1 1 1
1 1 1 1
Output:
3 2 1 0
4 -1 2 1
5 4 3 2
Example
Input
3 4
1 1 1 0
1 -1 1 1
1 1 1 1
Output
3 2 1 0
4 -1 2 1
5 4 3 2