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;

}

};

417. Pacific Atlantic Water Flow ---M ！！！！

 There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

 

Example 1:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean 
       [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean 
       [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean 
       [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean 
       [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean 
       [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean 
       [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean 
       [4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2:

Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

 

Constraints:

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 105

A:

就是dfs ， 思路简单， 需要注意的是：位操作的时候，容易出错

下面的这个，思路是从每个位置，开始做dfs， 先检查四周。然后看是不是可以走比他低的位置。

class Solution {

public:

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {

// 000 is undecided, 001 for checking,

// 0B10 for Pacific, 0B110 for Atlantic, OB110 for both

vector<vector<int>> res;

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

vector<vector<int>> Where(m, vector<int>(n, 0));

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

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

dfs(heights, Where, res, i, j);

return res;

}

private:

void dfs(vector<vector<int>>& H, vector<vector<int>>& W,

vector<vector<int>>& res, int i, int j) {

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

if (W[i][j] >= 1)

return;

W[i][j] = 1;

if (i == 0 || j == 0)

W[i][j] |= 0B10;

if (i == m - 1 || j == n - 1)

W[i][j] |= 0B100;

int curHeight = H[i][j];

if (i + 1 < m && H[i + 1][j] <= curHeight) {

dfs(H, W, res, i + 1, j);

W[i][j] |= W[i + 1][j];

}

if (i - 1 >= 0 && H[i - 1][j] <= curHeight) {

dfs(H, W, res, i - 1, j);

W[i][j] |= W[i - 1][j];

}

if (j + 1 < n && H[i][j + 1] <= curHeight) {

dfs(H, W, res, i, j + 1);

W[i][j] |= W[i][j + 1];

}

if (j - 1 >= 0 && H[i][j - 1] <= curHeight) {

dfs(H, W, res, i, j - 1);

W[i][j] |= W[i][j - 1];

}

if (W[i][j] >= 6)

res.push_back({i, j});

}

};

然而，上面的是有问题的。如果没有检查完，而只是检查中， 就不继续。

会导致neighbor没有拿到其从他这个位置可以走到的海。

试着改了，加上finished 状态. 可是那样会导致stack overflow。 更惨。

更新后的解法。是从4个边，分别走。 然后再检查2个结果。这样就不需要一个mask 走2遍了。（那样容易出错）

PS： 看了chatgpt的推荐。

class Solution {

public:

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {

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

// 0 for white, 1 for gray, 2 for black, 4 for can_reach

vector<vector<int>> P(m, vector<int>(n, 0));

vector<vector<int>> A(m, vector<int>(n, 0));

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

dfs(heights, P, i, 0);

dfs(heights, A, i, n - 1);

}

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

dfs(heights, P, 0, j);

dfs(heights, A, m - 1, j);

}

vector<vector<int>> res;

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

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

if ((P[i][j] & 4) && (A[i][j] & 4))

res.push_back({i, j});

return res;

}

private:

void dfs(vector<vector<int>>& H, vector<vector<int>>& Flag, int i, int j) {

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

if (Flag[i][j] != 0)

return;

Flag[i][j] |= (4 + 1); // 4 for can reach, 1 for gray

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

for (auto step : steps) {

int x = i + step[0], y = j + step[1];

if (x >= 0 && x < m && y >= 0 && y < n && (H[x][y] >= H[i][j])) {

dfs(H, Flag, x, y);

}

}

Flag[i][j] |= 2; // 2 for marked as black , i.e. done

}

};