#179MediumGraphs· Multi-Source BFS

Spreading Outage

A data centre floor is laid out as a grid of rack positions. Each cell holds `0` (no rack), `1` (a healthy rack) or `2` (a failed rack). Every minute, every healthy rack that shares an edge (up, down, left or right) with a failed rack also fails. Empty cells never fail and do not pass the failure on. Return the minimum number of minutes until no healthy rack is left. If some healthy rack can never fail because failures cannot reach it, return `-1`. If there are no healthy racks to begin with, return `0`.

Input format

`floor`: a rectangular grid of integers, each 0, 1 or 2.

Output format

An integer: the number of minutes until all racks have failed, or -1 if impossible.

Examples

Input: floor = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]

Output: 4

The failure spreads outward each minute and the last healthy rack, in the bottom right corner, fails after 4 minutes.

Input: floor = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]

Output: -1

The rack at the bottom left is cut off by empty cells and never fails: -1.

Input: floor = [[0, 2]]

Output: 0

There is no healthy rack, so no time is needed.

Constraints

1 <= rows, columns <= 50
floor[r][c] is 0, 1 or 2.

Study first

Graphs and Traversal: BFS and DFS

#graph
#breadth-first-search
#matrix
#multi-source