DFS 算法秒殺五道島嶼問題
本文轉(zhuǎn)載自微信公眾號「labuladong」，作者labuladong。轉(zhuǎn)載本文請聯(lián)系labuladong公眾號。
島嶼問題是經(jīng)典的面試高頻題，雖然基本的島嶼問題并不難，但是島嶼問題有一些有意思的擴展，比如求子島嶼數(shù)量，求形狀不同的島嶼數(shù)量等等，本文就來把這些問題一網(wǎng)打盡。
島嶼系列問題的核心考點就是用 DFS/BFS 算法遍歷二維數(shù)組。
本文主要來講解如何用 DFS 算法來秒殺島嶼系列問題，不過用 BFS 算法的核心思路是完全一樣的，無非就是把 DFS 改寫成 BFS 而已。
那么如何在二維矩陣中使用 DFS 搜索呢?如果你把二維矩陣中的每一個位置看做一個節(jié)點，這個節(jié)點的上下左右四個位置就是相鄰節(jié)點，那么整個矩陣就可以抽象成一幅網(wǎng)狀的「圖」結(jié)構(gòu)。
根據(jù) 學習數(shù)據(jù)結(jié)構(gòu)和算法的框架思維，完全可以根據(jù)二叉樹的遍歷框架改寫出二維矩陣的 DFS 代碼框架：
- // 二叉樹遍歷框架
- void traverse(TreeNode root) {
- traverse(root.left);
- traverse(root.right);
- }
- // 二維矩陣遍歷框架
- void dfs(int[][] grid, int i, int j, boolean[] visited) {
- int m = grid.length, n = grid[0].length;
- if (i < 0 || j < 0 || i >= m || j >= n) {
- // 超出索引邊界
- return;
- }
- if (visited[i][j]) {
- // 已遍歷過 (i, j)
- return;
- }
- // 進入節(jié)點 (i, j)
- visited[i][j] = true;
- dfs(grid, i - 1, j); // 上
- dfs(grid, i + 1, j); // 下
- dfs(grid, i, j - 1); // 左
- dfs(grid, i, j + 1); // 右
- // 離開節(jié)點 (i, j)
- visited[i][j] = false;
- }
因為二維矩陣本質(zhì)上是一幅「圖」，所以遍歷的過程中需要一個visited布爾數(shù)組防止走回頭路，如果你能理解上面這段代碼，那么搞定所有島嶼問題都很簡單。
這里額外說一個處理二維數(shù)組的常用小技巧，你有時會看到使用「方向數(shù)組」來處理上下左右的遍歷，和前文 圖遍歷框架 的代碼很類似：
- // 方向數(shù)組，分別代表上、下、左、右
- int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
- void dfs(int[][] grid, int i, int j, boolean[] visited) {
- int m = grid.length, n = grid[0].length;
- if (i < 0 || j < 0 || i >= m || j >= n) {
- // 超出索引邊界
- return;
- }
- if (visited[i][j]) {
- // 已遍歷過 (i, j)
- return;
- }
- // 進入節(jié)點 (i, j)
- visited[i][j] = true;
- // 遞歸遍歷上下左右的節(jié)點
- for (int[] d : dirs) {
- int next_i = i + d[0];
- int next_j = j + d[1];
- dfs(grid, next_i, next_j);
- }
- // 離開節(jié)點 (i, j)
- visited[i][j] = false;
- }
這種寫法無非就是用 for 循環(huán)處理上下左右的遍歷罷了，你可以按照個人喜好選擇寫法。
島嶼數(shù)量
這是力扣第 200 題「島嶼數(shù)量」，最簡單也是最經(jīng)典的一道島嶼問題，題目會輸入一個二維數(shù)組grid，其中只包含0或者1，0代表海水，1代表陸地，且假設(shè)該矩陣四周都是被海水包圍著的。
我們說連成片的陸地形成島嶼，那么請你寫一個算法，計算這個矩陣grid中島嶼的個數(shù)，函數(shù)簽名如下：
- int numIslands(char[][] grid);
比如說題目給你輸入下面這個grid有四片島嶼，算法應(yīng)該返回 4：
思路很簡單，關(guān)鍵在于如何尋找并標記「島嶼」，這就要 DFS 算法發(fā)揮作用了，我們直接看解法代碼：
- // 主函數(shù)，計算島嶼數(shù)量
- int numIslands(char[][] grid) {
- int res = 0;
- int m = grid.length, n = grid[0].length;
- // 遍歷 grid
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- if (grid[i][j] == '1') {
- // 每發(fā)現(xiàn)一個島嶼，島嶼數(shù)量加一
- res++;
- // 然后使用 DFS 將島嶼淹了
- dfs(grid, i, j);
- }
- }
- }
- return res;
- }
- // 從 (i, j) 開始，將與之相鄰的陸地都變成海水
- void dfs(char[][] grid, int i, int j) {
- int m = grid.length, n = grid[0].length;
- if (i < 0 || j < 0 || i >= m || j >= n) {
- // 超出索引邊界
- return;
- }
- if (grid[i][j] == '0') {
- // 已經(jīng)是海水了
- return;
- }
- // 將 (i, j) 變成海水
- grid[i][j] = '0';
- // 淹沒上下左右的陸地
- dfs(grid, i + 1, j);
- dfs(grid, i, j + 1);
- dfs(grid, i - 1, j);
- dfs(grid, i, j - 1);
- }
為什么每次遇到島嶼，都要用 DFS 算法把島嶼「淹了」呢?主要是為了省事，避免維護visited數(shù)組。
因為dfs函數(shù)遍歷到值為0的位置會直接返回，所以只要把經(jīng)過的位置都設(shè)置為0，就可以起到不走回頭路的作用。
PS：這類 DFS 算法還有個別名叫做 FloodFill 算法，現(xiàn)在有沒有覺得 FloodFill 這個名字還挺貼切的~
這個最最基本的島嶼問題就說到這，我們來看看后面的題目有什么花樣。
封閉島嶼的數(shù)量
上一題說二維矩陣四周可以認為也是被海水包圍的，所以靠邊的陸地也算作島嶼。
力扣第 1254 題「統(tǒng)計封閉島嶼的數(shù)目」和上一題有兩點不同：
1、用0表示陸地，用1表示海水。
2、讓你計算「封閉島嶼」的數(shù)目。所謂「封閉島嶼」就是上下左右全部被1包圍的0，也就是說靠邊的陸地不算作「封閉島嶼」。
函數(shù)簽名如下：
- int closedIsland(int[][] grid)
比如題目給你輸入如下這個二維矩陣：
算法返回 2，只有圖中灰色部分的0是四周全都被海水包圍著的「封閉島嶼」。
那么如何判斷「封閉島嶼」呢?其實很簡單，把上一題中那些靠邊的島嶼排除掉，剩下的不就是「封閉島嶼」了嗎?
有了這個思路，就可以直接看代碼了，注意這題規(guī)定0表示陸地，用1表示海水：
- // 主函數(shù)：計算封閉島嶼的數(shù)量
- int closedIsland(int[][] grid) {
- int m = grid.length, n = grid[0].length;
- for (int j = 0; j < n; j++) {
- // 把靠上邊的島嶼淹掉
- dfs(grid, 0, j);
- // 把靠下邊的島嶼淹掉
- dfs(grid, m - 1, j);
- }
- for (int i = 0; i < m; i++) {
- // 把靠左邊的島嶼淹掉
- dfs(grid, i, 0);
- // 把靠右邊的島嶼淹掉
- dfs(grid, i, n - 1);
- }
- // 遍歷 grid，剩下的島嶼都是封閉島嶼
- int res = 0;
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- if (grid[i][j] == 0) {
- res++;
- dfs(grid, i, j);
- }
- }
- }
- return res;
- }
- // 從 (i, j) 開始，將與之相鄰的陸地都變成海水
- void dfs(int[][] grid, int i, int j) {
- int m = grid.length, n = grid[0].length;
- if (i < 0 || j < 0 || i >= m || j >= n) {
- return;
- }
- if (grid[i][j] == 1) {
- // 已經(jīng)是海水了
- return;
- }
- // 將 (i, j) 變成海水
- grid[i][j] = 1;
- // 淹沒上下左右的陸地
- dfs(grid, i + 1, j);
- dfs(grid, i, j + 1);
- dfs(grid, i - 1, j);
- dfs(grid, i, j - 1);
- }
只要提前把靠邊的陸地都淹掉，然后算出來的就是封閉島嶼了。
PS：處理這類島嶼問題除了 DFS/BFS 算法之外，Union Find 并查集算法也是一種可選的方法，前文 Union Find 算法運用 就用 Union Find 算法解決了一道類似的問題。
這道島嶼題目的解法稍微改改就可以解決力扣第 1020 題「飛地的數(shù)量」，這題不讓你求封閉島嶼的數(shù)量，而是求封閉島嶼的面積總和。
其實思路都是一樣的，先把靠邊的陸地淹掉，然后去數(shù)剩下的陸地數(shù)量就行了，注意第 1020 題中1代表陸地，0代表海水：
- int numEnclaves(int[][] grid) {
- int m = grid.length, n = grid[0].length;
- // 淹掉靠邊的陸地
- for (int i = 0; i < m; i++) {
- dfs(grid, i, 0);
- dfs(grid, i, n - 1);
- }
- for (int j = 0; j < n; j++) {
- dfs(grid, 0, j);
- dfs(grid, m - 1, j);
- }
- // 數(shù)一數(shù)剩下的陸地
- int res = 0;
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- if (grid[i][j] == 1) {
- res += 1;
- }
- }
- }
- return res;
- }
- // 和之前的實現(xiàn)類似
- void dfs(int[][] grid, int i, int j) {
- // ...
- }
篇幅所限，具體代碼我就不寫了，我們繼續(xù)看其他的島嶼問題。
島嶼的最大面積
這是力扣第 695 題「島嶼的最大面積」，0表示海水，1表示陸地，現(xiàn)在不讓你計算島嶼的個數(shù)了，而是讓你計算最大的那個島嶼的面積，函數(shù)簽名如下：
- int maxAreaOfIsland(int[][] grid)
比如題目給你輸入如下一個二維矩陣：
其中面積最大的是橘紅色的島嶼，算法返回它的面積 6。
這題的大體思路和之前完全一樣，只不過dfs函數(shù)淹沒島嶼的同時，還應(yīng)該想辦法記錄這個島嶼的面積。
我們可以給dfs函數(shù)設(shè)置返回值，記錄每次淹沒的陸地的個數(shù)，直接看解法吧：
- int maxAreaOfIsland(int[][] grid) {
- // 記錄島嶼的最大面積
- int res = 0;
- int m = grid.length, n = grid[0].length;
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- if (grid[i][j] == 1) {
- // 淹沒島嶼，并更新最大島嶼面積
- res = Math.max(res, dfs(grid, i, j));
- }
- }
- }
- return res;
- }
- // 淹沒與 (i, j) 相鄰的陸地，并返回淹沒的陸地面積
- int dfs(int[][] grid, int i, int j) {
- int m = grid.length, n = grid[0].length;
- if (i < 0 || j < 0 || i >= m || j >= n) {
- // 超出索引邊界
- return 0;
- }
- if (grid[i][j] == 0) {
- // 已經(jīng)是海水了
- return 0;
- }
- // 將 (i, j) 變成海水
- grid[i][j] = 0;
- return dfs(grid, i + 1, j)
- + dfs(grid, i, j + 1)
- + dfs(grid, i - 1, j)
- + dfs(grid, i, j - 1) + 1;
- }
解法和之前相比差不多，我也不多說了，接下來的兩道島嶼問題是比較有技巧性的，我們重點來看一下。
子島嶼數(shù)量
如果說前面的題目都是模板題，那么力扣第 1905 題「統(tǒng)計子島嶼」可能得動動腦子了：
這道題的關(guān)鍵在于，如何快速判斷子島嶼?肯定可以借助 Union Find 并查集算法 來判斷，不過本文重點在 DFS 算法，就不展開并查集算法了。
什么情況下grid2中的一個島嶼B是grid1中的一個島嶼A的子島?
當島嶼B中所有陸地在島嶼A中也是陸地的時候，島嶼B是島嶼A的子島。
反過來說，如果島嶼B中存在一片陸地，在島嶼A的對應(yīng)位置是海水，那么島嶼B就不是島嶼A的子島。
那么，我們只要遍歷grid2中的所有島嶼，把那些不可能是子島的島嶼排除掉，剩下的就是子島。
依據(jù)這個思路，可以直接寫出下面的代碼：
- int countSubIslands(int[][] grid1, int[][] grid2) {
- int m = grid1.length, n = grid1[0].length;
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- if (grid1[i][j] == 0 && grid2[i][j] == 1) {
- // 這個島嶼肯定不是子島，淹掉
- dfs(grid2, i, j);
- }
- }
- }
- // 現(xiàn)在 grid2 中剩下的島嶼都是子島，計算島嶼數(shù)量
- int res = 0;
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- if (grid2[i][j] == 1) {
- res++;
- dfs(grid2, i, j);
- }
- }
- }
- return res;
- }
- // 從 (i, j) 開始，將與之相鄰的陸地都變成海水
- void dfs(int[][] grid, int i, int j) {
- int m = grid.length, n = grid[0].length;
- if (i < 0 || j < 0 || i >= m || j >= n) {
- return;
- }
- if (grid[i][j] == 0) {
- return;
- }
- grid[i][j] = 0;
- dfs(grid, i + 1, j);
- dfs(grid, i, j + 1);
- dfs(grid, i - 1, j);
- dfs(grid, i, j - 1);
- }
這道題的思路和計算「封閉島嶼」數(shù)量的思路有些類似，只不過后者排除那些靠邊的島嶼，前者排除那些不可能是子島的島嶼。
不同的島嶼數(shù)量
這是本文的最后一道島嶼題目，作為壓軸題，當然是最有意思的。
力扣第 694 題「不同的島嶼數(shù)量」，題目還是輸入一個二維矩陣，0表示海水，1表示陸地，這次讓你計算 不同的 (distinct) 島嶼數(shù)量，函數(shù)簽名如下：
- int numDistinctIslands(int[][] grid)
比如題目輸入下面這個二維矩陣：
其中有四個島嶼，但是左下角和右上角的島嶼形狀相同，所以不同的島嶼共有三個，算法返回 3。
很顯然我們得想辦法把二維矩陣中的「島嶼」進行轉(zhuǎn)化，變成比如字符串這樣的類型，然后利用 HashSet 這樣的數(shù)據(jù)結(jié)構(gòu)去重，最終得到不同的島嶼的個數(shù)。
如果想把島嶼轉(zhuǎn)化成字符串，說白了就是序列化，序列化說白了遍歷嘛，前文 二叉樹的序列化和反序列化 講了二叉樹和字符串互轉(zhuǎn)，這里也是類似的。
首先，對于形狀相同的島嶼，如果從同一起點出發(fā)，dfs函數(shù)遍歷的順序肯定是一樣的。
因為遍歷順序是寫死在你的遞歸函數(shù)里面的，不會動態(tài)改變：
- void dfs(int[][] grid, int i, int j) {
- // 遞歸順序：
- dfs(grid, i - 1, j); // 上
- dfs(grid, i + 1, j); // 下
- dfs(grid, i, j - 1); // 左
- dfs(grid, i, j + 1); // 右
- }
所以，遍歷順序從某種意義上說就可以用來描述島嶼的形狀，比如下圖這兩個島嶼：
假設(shè)它們的遍歷順序是：
下，右，上，撤銷上，撤銷右，撤銷下
如果我用分別用1, 2, 3, 4代表上下左右，用-1, -2, -3, -4代表上下左右的撤銷，那么可以這樣表示它們的遍歷順序：
2, 4, 1, -1, -4, -2
你看，這就相當于是島嶼序列化的結(jié)果，只要每次使用dfs遍歷島嶼的時候生成這串數(shù)字進行比較，就可以計算到底有多少個不同的島嶼了。
要想生成這段數(shù)字，需要稍微改造dfs函數(shù)，添加一些函數(shù)參數(shù)以便記錄遍歷順序：
- void dfs(int[][] grid, int i, int j, StringBuilder sb, int dir) {
- int m = grid.length, n = grid[0].length;
- if (i < 0 || j < 0 || i >= m || j >= n
- || grid[i][j] == 0) {
- return;
- }
- // 前序遍歷位置：進入 (i, j)
- grid[i][j] = 0;
- sb.append(dir).append(',');
- dfs(grid, i - 1, j, sb, 1); // 上
- dfs(grid, i + 1, j, sb, 2); // 下
- dfs(grid, i, j - 1, sb, 3); // 左
- dfs(grid, i, j + 1, sb, 4); // 右
- // 后序遍歷位置：離開 (i, j)
- sb.append(-dir).append(',');
- }
dir記錄方向，dfs函數(shù)遞歸結(jié)束后，sb記錄著整個遍歷順序，其實這就是前文 回溯算法核心套路 說到的回溯算法框架，你看到頭來這些算法都是相通的。
有了這個dfs函數(shù)就好辦了，我們可以直接寫出最后的解法代碼：
- int numDistinctIslands(int[][] grid) {
- int m = grid.length, n = grid[0].length;
- // 記錄所有島嶼的序列化結(jié)果
- HashSet<String> islands = new HashSet<>();
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- if (grid[i][j] == 1) {
- // 淹掉這個島嶼，同時存儲島嶼的序列化結(jié)果
- StringBuilder sb = new StringBuilder();
- // 初始的方向可以隨便寫，不影響正確性
- dfs(grid, i, j, sb, 666);
- islands.add(sb.toString());
- }
- }
- }
- // 不相同的島嶼數(shù)量
- return islands.size();
- }
這樣，這道題就解決了，至于為什么初始調(diào)用dfs函數(shù)時的dir參數(shù)可以隨意寫，這里涉及 DFS 和回溯算法的一個細微差別，前文 圖算法基礎(chǔ) 有寫，這里就不展開了。
以上就是全部島嶼系列問題的解題思路，也許前面的題目大部分人會做，但是最后兩題還是比較巧妙的，希望本文對你有幫助。
