作者丨小小算法
來源丨小小算法（xiaoxiaosuanfa）
一道題看透DFS和BFS你知道 DFS 和 BFS 是哪幾個英文單詞的縮寫嗎？(手動滑稽)。DFS: Depth First Search (深度優先搜索)BFS: Breadth First Search (廣度優先搜索)DFS 和 BFS 都是常用來遍歷搜索樹或圖的算法。二叉樹中的前序、中序和後序遍歷都屬於DFS，層次遍歷屬於BFS。DFS常用遞歸和棧來實現，BFS常用隊列來實現。今天我們通過leetcode 1254. 統計封閉島嶼的數目(https://leetcode-cn.com/problems/number-of-closed-islands/) 來練習DFS和BFS.題目描述有一個二維矩陣 grid ，每個位置要麼是陸地（記號為 0 ）要麼是水域（記號為 1 ）。我們從一塊陸地出發，每次可以往上下左右 4 個方向相鄰區域走，能走到的所有陸地區域，我們將其稱為一座「島嶼」。如果一座島嶼 完全 由水域包圍，即陸地邊緣上下左右所有相鄰區域都是水域，那麼我們將其稱為 「封閉島嶼」。輸入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]解釋：灰色區域的島嶼是封閉島嶼，因為這座島嶼完全被水域包圍（即被 1 區域包圍）。解題思路題目要我們求出封閉島嶼的個數，那我們可以先遍歷矩陣中的每一個位置，如果當前位置為0(陸地)，我們就需要判斷該位置所在的島嶼是否為封閉島嶼。那如何找到該位置所在的島嶼呢？當然就是從該位置出發向四個方向遍歷了。這屬於遍歷一塊區域內的所有內容，使用DFS 和 BFS 都可以。int closedIsland(vector<vector<int>>& grid) {
int ret = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 0) {
ret += dfs(grid, i, j);
//或者使用BFS
//ret += bfs(grid, i, j);
}
}
}
return ret;
}
if (r < 0 || r >= grid.size() || r < 0 || c >= grid[0].size()) {
return 0;
}
if (grid[r][c] == 1) {
return 1;
}
int dfs(vector<vector<int>>& grid, int r, int c) {
if (r < 0 || r >= grid.size() || r < 0 || c >= grid[0].size()) {
return 0;
}
if (grid[r][c] == 1) {
return 1;
}
grid[r][c] = 1;
int vr[] = {0, 1, 0, -1};
int vc[] = {1, 0, -1, 0};
int ret = 1;
for (int i = 0; i < 4; i++) {
ret = min(ret, dfs(grid, r+vr[i], c+vc[i]));
}
return ret;
}
dfs(grid, r, c+1);
dfs(grid, r+1, c);
dfs(grid, r-1, c);
dfs(grid, r, c-1);
for (int i = 0; i < 4; i++) {
ret = min(ret, dfs(grid, r+vr[i], c+vc[i]));
if (ret == 0) {
return 0;
}
}
int bfs(vector<vector<int>>& grid, int r, int c) {
int ret = 1;
queue<vector<int>> q;
q.push({r, c});
while (!q.empty()) {
vector<int> pos(q.front());
q.pop();
grid[pos[0]][pos[1]] = 1;
int vr[] = {0, 1, 0, -1};
int vc[] = {1, 0, -1, 0};
for (int i = 0; i < 4; i++) {
int curr = pos[0] + vr[i];
int curc = pos[1] + vc[i];
if (curr < 0 || curr >= grid.size() || curc < 0 || curc >= grid[0].size()) {
ret = 0;
continue;
}
if (grid[curr][curc] == 0) {
q.push({curr, curc});
}
}
}
return ret;
}