994. Rotting Oranges -- M

 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.

A:

典型的BFS， 需要注意的就是 极端的，全空， 全1， 的情况

class Solution {

public:

int orangesRotting(vector<vector<int>>& grid) {

int m = grid.size(), n = grid[0].size();

vector<pair<int, int>> V;

bool hasOrange = false;

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++) {

if (grid[i][j] == 2)

V.push_back({i, j});

if (grid[i][j] == 1)

hasOrange = true;

}

if (not hasOrange)

return 0;

if (V.empty()) // else has only 1

return -1;

int res = -1;

while (not V.empty()) {

res++;

V = bfs(grid, V);

}

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

if (grid[i][j] == 1)

return -1;

return res;

}

private:

vector<pair<int, int>> bfs(vector<vector<int>>& grid,

vector<pair<int, int>>& V) {

int m = grid.size(), n = grid[0].size();

vector<vector<int>> step = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

vector<pair<int, int>> newV;

for (const auto& v : V) {

for (auto s : step) {

int x = v.first + s[0], y = v.second + s[1];

if (x >= 0 && x < m && y >= 0 && y < n) {

if (grid[x][y] == 1) {

newV.push_back({x, y});

grid[x][y] = 2;

}

}

}

}

return newV;

}

};

但是，上面的效率不行。 才beat  5%   感觉是因为每次生成的新的数组。 需要一层层地跑。

----------------------- 把递归改成循环----------

class Solution {

public:

int orangesRotting(vector<vector<int>>& grid) {

int m = grid.size(), n = grid[0].size();

vector<pair<int, int>> V;

int freshOrange = 0;

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++) {

if (grid[i][j] == 2)

V.push_back({i, j});

if (grid[i][j] == 1)

freshOrange++;

}

if (freshOrange == 0)

return 0;

if (V.empty()) // has no rotten orange

return -1;

int res = 0, start = 0;

vector<vector<int>> Step = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

while (true) {

int oldSize = V.size();

for (int i = start; i < oldSize; i++) {

for (auto s : Step) {

int x = V[i].first + s[0], y = V[i].second + s[1];

if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {

V.push_back({x, y});

grid[x][y] = 2;

freshOrange--;

}

}

}

if (oldSize < V.size()) { // check with the new

res++;

} else {

break;

}

start = oldSize;

}

return freshOrange == 0 ? res : -1;

}

};