Enqueue all target cells at once and perform multi-source BFS outward.

Walls and Gates

medium

Acceptance: 53%

GraphsBFS

An m-by-n grid contains walls (-1), target locations (0), and open spaces (marked with a large sentinel value). Replace each open space's value with the shortest distance to any target. Leave walls and unreachable spaces unchanged.

Examples

Example 1:

Input:rooms = [[2147483647,0,2147483647],[2147483647,-1,2147483647],[2147483647,2147483647,0]]

Output:[[1,0,1],[2,-1,1],[3,2,0]]

Explanation: Each open space is filled with its shortest distance to a target location.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Walls and Gates

Examples

Hints

Related Problems