Grid Propagation Time

You are given an m x n integer grid grid where each cell holds one of three values:

• 0 is an empty cell,
• 1 is a clean cell, or
• 2 is an infected cell.

Each step, every infected cell infects its 4-directionally adjacent (up, down, left, or right, never diagonally) clean cells.

Return the minimum number of steps that must pass until no cell in the grid is clean. If this is impossible because some clean cell can never be reached, return -1 instead. If there are no clean cells to begin with, return 0.

Examples

Example 1

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The clean cell in the bottom-left (row 2, column 0) is never infected: infection only spreads up/down/left/right, and no such path reaches it.

Example 3

Input: grid = [[0,2]]
Output: 0
Explanation: There are no clean cells to begin with, so zero steps pass.