目錄
1? 200. 島嶼數量
2? 994. 腐爛的橘子
2.1? 智障遍歷法
2.2? 仿層序遍歷法
菜鳥做題，語言是 C++
1? 200. 島嶼數量
解題思路：
- 遍歷二維數組，尋找 “1”（若找到則島嶼數量 +1）
- 尋找與當前 “1” 直接或間接連接在一起的 “1”
- 將這些 “1” 置為 “0”，再尋找下一個 “1”
思路說明圖：
如步驟 1 所示，我們找到 “1”（紅框內部），它可以作為一個島嶼的開頭。接下來，我們尋找與這個 “1” 直接或間接連接在一起的 “1”，如步驟 2 所示。這一坨 “1”（紅框內部）構成一個島嶼。
直接連接 是指上下左右四個方向，斜對角方向的不算。
除此之外，為了避免我們下一次尋找 “1” 時，把這座島嶼內部的 “1” 視為下一個島嶼的開頭，我們要將這些 “1” 置為 “0” 。
我們是對整個二維數組進行遍歷的，若不在遍歷完一座島嶼后將 “1” 置為 “0”，那么這座島嶼除開頭之外的 “1” 會被誤認為是下一座島嶼的開頭。
具體代碼：
① Find “1”：在二維數組中尋找 “1”，作為島嶼的開頭。
for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (grid[i][j] == '1') {++count;helper(grid, i, j);}}
}nr 是二維數組的行數，nc 是二維數組的列數。一旦找到 “1” 就 ++count，即認為找到了一座新的島嶼。同時，使用 helper 函數去尋找與當前 “1” 直接或間接連接在一起的 “1” 。
② Find Island：尋找與當前 “1” 直接或間接連接在一起的 “1”，它們構成一座島嶼。
void helper(vector<vector<char>>& grid, int r, int c) {int nr = grid.size();int nc = grid[0].size();grid[r][c] = '0';if (r - 1 >= 0 && grid[r - 1][c] == '1') helper(grid, r - 1, c);if (r + 1 < nr && grid[r + 1][c] == '1') helper(grid, r + 1, c);if (c - 1 >= 0 && grid[r][c - 1] == '1') helper(grid, r, c - 1);if (c + 1 < nc && grid[r][c + 1] == '1') helper(grid, r, c + 1);
}這四個 if 其實就是做上下左右四個方向的邊界判斷，同時判斷當前 “1” 的鄰居是不是 “1” 。若找到相鄰的 “1”，那么再遞歸尋找與相鄰的 “1” 直接或間接連接在一起的 “1” 。
class Solution {
public:void helper(vector<vector<char>>& grid, int r, int c) {int nr = grid.size();int nc = grid[0].size();grid[r][c] = '0';if (r - 1 >= 0 && grid[r - 1][c] == '1') helper(grid, r - 1, c);if (r + 1 < nr && grid[r + 1][c] == '1') helper(grid, r + 1, c);if (c - 1 >= 0 && grid[r][c - 1] == '1') helper(grid, r, c - 1);if (c + 1 < nc && grid[r][c + 1] == '1') helper(grid, r, c + 1);}int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if (nr == 0) return 0;int nc = grid[0].size();int count = 0;for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (grid[i][j] == '1') {++count;helper(grid, i, j);}}}return count;}
};2? 994. 腐爛的橘子
與? 200. 島嶼數量? 像又不像，區別在于是否有時間觀念
2.1? 智障遍歷法
解題思路：
- 每個時刻都遍歷二維數組，尋找腐爛的橘子（2）
- 對位于腐爛的橘子（2）四周的新鮮橘子（1）進行污染
- 直到所有新鮮橘子都被污染，或者無法繼續污染
具體代碼：
① 尋找腐爛的橘子（2），與 200 題的代碼幾乎一樣。
for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (temp[i][j] == 2)helper(grid, i, j);}
}② 對位于腐爛的橘子（2）四周的新鮮橘子（1）進行污染。
void helper(vector<vector<int>>& grid, int r, int c) {if (r - 1 >= 0 && grid[r - 1][c] == 1) grid[r - 1][c] = 2;if (r + 1 < nr && grid[r + 1][c] == 1) grid[r + 1][c] = 2;if (c - 1 >= 0 && grid[r][c - 1] == 1) grid[r][c - 1] = 2;if (c + 1 < nc && grid[r][c + 1] == 1) grid[r][c + 1] = 2;
}③ 判斷是否所有的新鮮橘子（1）都被污染。
bool isRotted(vector<vector<int>>& grid) {for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (grid[i][j] == 1) return false;}}return true;
}④ 判斷是否無法繼續污染：在進行新一輪污染之前，先把上一輪的污染結果 grid 存入 temp 中，如果這一輪污染后有 temp == grid，則說明已經無法繼續污染了。
vector<vector<int>> temp = grid;
for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (temp[i][j] == 2)helper(grid, i, j);}
}
if (temp == grid) return -1;這樣做還有一個好處，就是可以通過 if (temp[i][j] == 2) 來尋找腐爛的橘子，避免在這一輪中新腐爛的橘子參與到污染中。
class Solution {
public:int nr, nc;void helper(vector<vector<int>>& grid, int r, int c) {if (r - 1 >= 0 && grid[r - 1][c] == 1) grid[r - 1][c] = 2;if (r + 1 < nr && grid[r + 1][c] == 1) grid[r + 1][c] = 2;if (c - 1 >= 0 && grid[r][c - 1] == 1) grid[r][c - 1] = 2;if (c + 1 < nc && grid[r][c + 1] == 1) grid[r][c + 1] = 2;}bool isRotted(vector<vector<int>>& grid) {for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (grid[i][j] == 1) return false;}}return true;}int orangesRotting(vector<vector<int>>& grid) {nr = grid.size();nc = grid[0].size();int count = 0;while (!isRotted(grid)) {vector<vector<int>> temp = grid;for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (temp[i][j] == 2)helper(grid, i, j);}}if (temp == grid) return -1;++count;if (isRotted(grid)) return count;}return count;}
};2.2? 仿層序遍歷法
參考官方題解進行了升級，仿二叉樹的層序遍歷，不用像 2.1 那樣每次都進行全部遍歷
核心思想：將屬于同一時刻的腐爛橘子視為屬于同一層。
上圖畫出了橘子逐步腐爛的 5 個時刻，每個時刻中打紅叉的腐爛橘子屬于同一層，打灰叉的腐爛橘子屬于上一層。
解題思路：
- 將屬于同一時刻的腐爛橘子送入隊列中
- 出隊并遍歷屬于同一時刻的腐爛橘子
- 對四周的新鮮橘子進行污染并送入隊列中
思路說明圖：
對于時刻 1，讓腐爛的橘子入隊；對于時刻 2，隊列中的腐爛橘子出隊，讓它們對四周的新鮮橘子進行污染，最后將新被污染的橘子入隊。以此類推。
在一輪污染中，如果有橘子被污染，則計時器 +1，同時判斷新鮮橘子是否被污染完畢；如果沒有橘子被污染，則跳出循環，同時判斷新鮮橘子是否被污染完畢。若沒有橘子被污染且新鮮橘子沒有被污染完畢，則表明無法污染所有新鮮橘子。
具體代碼：
① 初始化：
- 計數新鮮橘子的數量，即 freshCount + 1
- 記錄腐爛橘子的位置，即將橫縱坐標送入隊列中
int freshCount = 0;
queue<pair<int, int>> q;
for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (grid[i][j] == 1) {++freshCount;} else if (grid[i][j] == 2) {q.push(make_pair(i, j));}}
}nr 是 grid 的行數，nc 是 grid 的列數。
② 循環結構和二叉樹的層序遍歷一模一樣：
- 獲取當前層中腐爛橘子的個數
- 遍歷當前層中的腐爛橘子
while (!q.empty()) {int currentSize = q.size();for (int i = 0; i < currentSize; ++i) {pair<int, int> pos = q.front();q.pop();// 對橘子進行污染}
}③ 針對每個腐爛橘子，對其四周進行污染：
- 判斷上/下/左/右位置是否越界，若越界則跳過該位置
- 若該位置上的是新鮮橘子，則進行污染并將其入隊
- 同時將污染標志置為 true，新鮮橘子數量 - 1
for (int i = 0; i < 4; ++i) {int x = pos.first + dir_x[i];int y = pos.second + dir_y[i];if (x < 0|| x >= nr || y < 0|| y >= nc || grid[x][y] == 0)continue;if (grid[x][y] == 1) {hasPolluted = true;--freshCount;grid[x][y] = 2;q.push(make_pair(x, y));}if (freshCount == 0) break;
}hasPolluted 用于表明當前層中是否至少有一個腐爛橘子造成了污染，如果沒有造成污染，那么就要考慮是否無法污染所有新鮮橘子了。
class Solution {
public:int dir_x[4] = {0, 1, 0, -1};int dir_y[4] = {1, 0, -1, 0};int orangesRotting(vector<vector<int>>& grid) {int nr = grid.size();if (nr == 0) return 0;int nc = grid[0].size();int freshCount = 0;queue<pair<int, int>> q;for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (grid[i][j] == 1) {++freshCount;} else if (grid[i][j] == 2) {q.push(make_pair(i, j));}}}int timeCount = 0;int hasPolluted = false;while (!q.empty()) {int currentSize = q.size();for (int i = 0; i < currentSize; ++i) {pair<int, int> pos = q.front();q.pop();for (int i = 0; i < 4; ++i) {int x = pos.first + dir_x[i];int y = pos.second + dir_y[i];if (x < 0|| x >= nr || y < 0|| y >= nc || grid[x][y] == 0)continue;if (grid[x][y] == 1) {hasPolluted = true;--freshCount;grid[x][y] = 2;q.push(make_pair(x, y));}if (freshCount == 0) break;}}if (hasPolluted) ++timeCount;hasPolluted = false;}return freshCount == 0 ? timeCount : -1;}
};技能點：使用循環結構來測試上/下/左/右四個方位。
int dir_x[4] = {0, 1, 0, -1};
int dir_y[4] = {1, 0, -1, 0};for (int i = 0; i < 4; ++i) {int x = pos.first + dir_x[i];int y = pos.second + dir_y[i];if (x < 0|| x >= nr || y < 0|| y >= nc)// ...
}并且用逆否命題來作為判斷條件，就不需要寫很多 && 了！
)
