Walls and Gates

**Problem Statement:** Given the required input arguments, write an efficient algorithm to solve the **Walls and Gates** problem. Implement the required logic as specified by standard definitions for this classic algorithmic challenge. **Hint / Expected Approach:** Multi-source BFS from all gates simultaneously **Edge Cases to Consider:** - (1) No gates in grid - (2) No empty rooms - (3) Room unreachable from any gate

Examples

Example 1

Input: [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]]

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

Explanation: Classic

Example 2

Input: [[0]]

Output: [[0]]

Explanation: Single gate

Example 3

Input: [[-1]]

Output: [[-1]]

Explanation: Single wall

Constraints

▪2 <= vertices <= 1000
▪0 <= edges <= 5000
▪Avoid infinite cycles during depth traversal

Watch Out For Edge Cases

▪No gates in grid
▪No empty rooms
▪Room unreachable from any gate

Frequently Asked At

AmazonGoogleMetaAdobeFlipkart

Back to Arena

medium

Graph