# 14 Days Study Plan to Crack Algo I

2022.03.16

Day 9

# 542. 01 Matrix

Given an `m x n`

binary matrix `mat`

, return *the distance of the nearest *`0`

* for each cell*.

The distance between two adjacent cells is `1`

.

**Example 1:**

**Input:** mat = [[0,0,0],[0,1,0],[0,0,0]]

**Output:** [[0,0,0],[0,1,0],[0,0,0]]

**Example 2:**

**Input:** mat = [[0,0,0],[0,1,0],[1,1,1]]

**Output:** [[0,0,0],[0,1,0],[1,2,1]]

**Constraints:**

`m == mat.length`

`n == mat[i].length`

`1 <= m, n <= 104`

`1 <= m * n <= 104`

`mat[i][j]`

is either`0`

or`1`

.- There is at least one
`0`

in`mat`

.

Solution explanation: https://leetcode.com/problems/01-matrix/discuss/1629356/BFS-Solution-with-explanation-and-visualization-JS

# 994. Rotting Oranges

You are given an `m x n`

`grid`

where each cell can have one of three values:

`0`

representing an empty cell,`1`

representing a fresh orange, or`2`

representing a rotten orange.

Every minute, any fresh orange that is **4-directionally adjacent** to a rotten orange becomes rotten.

Return *the minimum number of minutes that must elapse until no cell has a fresh orange*. If *this is impossible, return* `-1`

.

**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 orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

**Example 3:**

**Input:** grid = [[0,2]]

**Output:** 0

**Explanation:** Since there are already no fresh oranges at minute 0, the answer is just 0.

**Constraints:**

`m == grid.length`

`n == grid[i].length`

`1 <= m, n <= 10`

`grid[i][j]`

is`0`

,`1`

, or`2`

.