最近在刷力扣時遇見的問題，自己總結(jié)加上看了力扣大佬的知識總結(jié)寫下本篇文章，我們所熟悉的 DFS（深度優(yōu)先搜索）問題通常是在樹或者圖結(jié)構(gòu)上進行的。而我們今天要討論的 DFS 問題，是在一種「網(wǎng)格」結(jié)構(gòu)中進行的。島嶼問題是這類網(wǎng)格 DFS 問題的典型代表。網(wǎng)格結(jié)構(gòu)遍歷起來要比二叉樹復(fù)雜一些，如果沒有掌握一定的方法，DFS 代碼容易寫得冗長繁雜。

1.1網(wǎng)格問題基本概念

網(wǎng)格問題是由 m×n?個小方格組成一個網(wǎng)格，每個小方格與其上下左右四個方格認為是相鄰的，要在這樣的網(wǎng)格上進行某種搜索。島嶼問題是一類典型的網(wǎng)格問題。每個格子中的數(shù)字可能是 0 或者 1。 數(shù)字為1的格子連接起來就形成一個島嶼。

?1.2 DFS的基本結(jié)構(gòu)

首先我們要確定訪問的下一個節(jié)點以及停止的邊界，那么首先網(wǎng)格結(jié)構(gòu)中的每個格子可以向四周延伸，分別為上，下，左，右，對于格子(r,c)來說，對應(yīng)的四個坐標分別為(r+1,c)、(r-1,c)、(r,c-1)、(r,c+1)。

?

?其次超出格子的邊界是什么?是grid[r][c]出現(xiàn)下標越界異常的格子，也就是那些超出范圍的格子。

?

?這樣我們就得到了網(wǎng)格DFS遍歷的框架代碼：

public void infect(char[][] grid,int i ,int j){
//超出范圍if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length){return;}
//訪問上，下，左，右infect(grid,i+1,j);infect(grid,i-1,j);infect(grid,i,j+1);infect(grid,i,j-1);
}

1.3 如何避免重復(fù)遍歷

網(wǎng)格結(jié)構(gòu)的 DFS 與二叉樹的 DFS 最大的不同之處在于，遍歷中可能遇到遍歷過的結(jié)點。這是因為，網(wǎng)格結(jié)構(gòu)本質(zhì)上是一個「圖」，我們可以把每個格子看成圖中的結(jié)點，每個結(jié)點有向上下左右的四條邊。在圖中遍歷時，自然可能遇到重復(fù)遍歷結(jié)點。

?如何避免這樣的重復(fù)遍歷呢？答案是將已經(jīng)遍歷過的格子的值修改一下，每次走過一個格子就修改格子的值。以島嶼問題為例，我們需要在所有值為 1 的陸地格子上做 DFS 遍歷。每走過一個陸地格子，就把格子的值改為 2，這樣當我們遇到 2 的時候，就知道這是遍歷過的格子了。

public void infect(char[][] grid,int i ,int j){if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length ){return;}grid[i][j] = '2';infect(grid,i+1,j);infect(grid,i-1,j);infect(grid,i,j+1);infect(grid,i,j-1);}

二、島嶼經(jīng)典例題

2.1 島嶼數(shù)量

島嶼類問題的通用解法、DFS 遍歷框架 - 島嶼數(shù)量 - 力扣（LeetCode）

• 0 —— 海洋格子
• 1 —— 陸地格子（未遍歷過）
• 2 —— 陸地格子（已遍歷過）

class Solution {public int numIslands(char[][] grid) {int islandNum = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == '1'){infect(grid,i,j);islandNum++;}}}return islandNum;}public void infect(char[][] grid,int i ,int j){if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1'){return;}grid[i][j] = '2';infect(grid,i+1,j);infect(grid,i-1,j);infect(grid,i,j+1);infect(grid,i,j-1);}
}

2.2 島嶼的周長

463. 島嶼的周長 - 力扣（LeetCode）

給你一個由?'1'（陸地）和?'0'（水）組成的的二維網(wǎng)格，請你計算網(wǎng)格中島嶼的數(shù)量。

網(wǎng)格中的格子?水平和垂直?方向相連（對角線方向不相連）。整個網(wǎng)格被水完全包圍，但其中恰好有一個島嶼（或者說，一個或多個表示陸地的格子相連組成的島嶼）。

我們可以將島嶼的周長中的邊分為兩類，如下圖所示。黃色的邊是與網(wǎng)格邊界相鄰的周長，而藍色的邊是與海洋格子相鄰的周長。

當我們的 dfs 函數(shù)因為「坐標 (r, c) 超出網(wǎng)格范圍」返回的時候，實際上就經(jīng)過了一條黃色的邊；而當函數(shù)因為「當前格子是海洋格子」返回的時候，實際上就經(jīng)過了一條藍色的邊。

?本題我們可以再次嵌套DFS的框架，但是要增加幾處地方，實際上，島嶼的周長是計算島嶼全部的「邊緣」，而這些邊緣就是我們在 DFS 遍歷中，dfs?函數(shù)返回的位置。

class Solution {public int islandPerimeter(int[][] grid) {for (int r = 0; r < grid.length; r++) {for (int c = 0; c < grid[0].length; c++) {if (grid[r][c] == 1){return dfs(grid,r,c);}}}return 0;}public int dfs(int[][] grid,int r,int c){if (r < 0 || r >= grid.length ||c < 0 || c >= grid[0].length ){return 1;}if (grid[r][c] == 0){return 1;}if (grid[r][c] != 1){return 0;}grid[r][c] = 2;return dfs(grid,r-1,c)+dfs(grid,r+1,c)+dfs(grid,r,c-1)+dfs(grid,r,c+1);}
}

2.3 單詞搜索

79. 單詞搜索 - 力扣（LeetCode）

給定一個?m x n?二維字符網(wǎng)格?board?和一個字符串單詞?word?。如果?word?存在于網(wǎng)格中，返回?true?；否則，返回?false?。

?本題在使用上面的DFS框架時，要加上回溯，因為當搜索一次時，會更改當前的格子的值，

如果我在DFS的過程中不改矩陣的狀態(tài)，那我就會出現(xiàn)重復(fù)搜索的情況啊，這可不行，因此矩陣是必須得改的。那就只剩下一個辦法了，每次DFS的過程中修改矩陣，DFS完了再把矩陣給改回去唄，這就是回溯！

那么什么是剪枝呢？所謂剪枝就是我在dfs的時候，如果已經(jīng)找到一個正確的路徑了，換句話說已經(jīng)得到結(jié)果了，其實就沒必要繼續(xù)DFS了，直接返回結(jié)果即可。這就是剪枝。

給一下官方的說法：剪枝，就是減小樹的規(guī)模，盡早排除搜索樹中不必要的分支的一種手段。

class Solution {private boolean find;public boolean exist(char[][] board, String word) {if(board == null){return false;}int m = board.length,n = board[0].length;boolean[][] visited = new boolean[m][n];find = false;for(int i = 0;i < m;i++){for(int j = 0 ;j < n;j++){backtracking(i, j, board, word, visited, 0);}}return find;}/*** i,j,board：棋盤格及當前元素的坐標* word: 要搜索的目標單詞* visited：記錄當前格子是否已被訪問過* pos: 記錄目標單詞的字符索引，只有棋盤格字符和pos指向的字符一致時，才有機會繼續(xù)搜索接下來的字符；如果pos已經(jīng)過了目標單詞的尾部了，那么便說明找到目標單詞了*/public void backtracking(int i, int j, char[][] board, String word, boolean[][] visited, int pos){// 超出邊界、已經(jīng)訪問過、已找到目標單詞、棋盤格中當前字符已經(jīng)和目標字符不一致了if(i < 0 || i >= board.length || j <0 || j>=board[0].length || visited[i][j] || find || board[i][j] != word.charAt(pos)){return;}if(pos == word.length()-1){find = true;return;}visited[i][j] = true;// 修改當前節(jié)點狀態(tài)backtracking(i+1, j, board, word, visited, pos+1);  // 遍歷子節(jié)點backtracking(i-1, j, board, word, visited, pos+1);backtracking(i, j+1, board, word, visited, pos+1);backtracking(i, j-1, board, word, visited, pos+1);visited[i][j] = false; // 撤銷修改}
}

如果對你有幫助，麻煩雙擊三連一下，謝謝啦！