文章目錄
-
- 網格類DFS
-
- 1. 周遊過的島嶼需要标記
- 2. 周遊過的島嶼需要再次使用的情況
網格類DFS
我把此類問題歸納為網格類的DFS,典型例題為島嶼标記,下面是該體型類模版,類似題都是根據該模版變形。
模闆
1. 周遊過的島嶼需要标記
class Solution {
public:
int numIslands(vector<vector<char>> &grid)
{
int count = 0;
if (grid.size() == 0) return 0;
//周遊網格
for(int i = 0; i < grid.size(); i++) {
for(int j = 0; j < grid[i].size(); j++) {
//如果該格子是1,則該1進行dfs得到連接配接的所有1組成一個島嶼
if(grid[i][j] == '1') {
dfs(grid, i, j);
count++;//組成島嶼後島嶼數量加一
}
}
}
return count;
}
void dfs(vector<vector<char>> &grid, int row, int col) {
//判斷是否到邊界,超過邊界則return
if(row < 0 || row > grid.size()-1 || col < 0 || col > grid[0].size()-1) return;
//如果目前為1則我們把它标記為2, 如果不是1則我們就return,該點不繼續遞歸
//這裡走過的要做标記是為了防止回頭周遊,走過的就不走了
if(grid[row][col] == '1') grid[row][col] = '2';
else return;
//上下左右遞歸
dfs(grid, row-1, col);
dfs(grid, row+1, col);
dfs(grid, row, col-1);
dfs(grid, row, col+1);
}
};
-
- 島嶼數量
-
- 島嶼的周長
-
- 島嶼的最大面積
-
- 不同島嶼的數量
-
- 圖像渲染
-
- 被圍繞的區域
- 劍指 Offer 13. 機器人的運動範圍
2. 周遊過的島嶼需要再次使用的情況
上述幾個題周遊過的島嶼标記後就不會再次周遊,而下面幾題會在标記後再次使用,這就需要在後序周遊處使用回溯,将已标記的島嶼撤銷标記
//如果目前島嶼的下一個島嶼傳回true也就是找到了,則可以傳回了,不需要繼續遞歸了
if( dfs(board, row-1, col, index) ||
dfs(board, row+1, col, index) ||
dfs(board, row, col-1, index) ||
dfs(board, row, col+1, index) == true) {
return true;
}
//回溯:這裡是後序周遊執行代碼,也就是說我們DFS一條ABC之後,會往回走一遍,也就是向父節點傳回
//當往回走的時候,我們把目前節點值還原成原字元,因為後面再次查找路徑的時候會使用該字元
board[row][col] = temp;
return false;
}
-
- 單詞搜尋(注意這裡要判斷下一個島嶼,不然逾時)