Graph BFS / DFS
LC #994Medium
Rotting Oranges
Graph BFS / DFS
AmazonGoogleMetaBloombergProblem
Find how many minutes until all oranges are rotten. Rotten oranges infect adjacent fresh oranges each minute.
graphbfsmatrix
Constraints
- ›1 ≤ m, n ≤ 10
- ›grid[i][j] is 0 (empty), 1 (fresh), or 2 (rotten)
- ›Return -1 if impossible to rot all oranges
Example
Input
grid = [[2,1,1],[1,1,0],[0,1,1]]Output
4Why
Rotten orange at [0,0] spreads: after 4 minutes all fresh oranges are rotten