LeetCode算法题7：DFS和BFS
文章目錄
- 前言
- 深度優先搜索算法偽代碼：
- 廣度優先搜索算法偽代碼：
- 一、圖像渲染
- DFS：
- BFS：
- 上面BFS算法存在的問題：
- 修改 1：
- 修改 2：
- 二、島嶼的最大面積
- DFS：
- BFS ：
- 三、合并二叉樹
- DFS：
- BFS：
- 上面BFS算法存在的問題：
- 修改 1：
- 修改 2：
- 四、填充每個節點的下一個右側節點指針
- 思路 1：
- 樹的層序遍歷
- 思路 2：
- 五、01矩陣
- BFS：
- DP：
- 六、腐爛的橘子
- BFS：
- 總結
前言
??????Leetcode算法系列：https://leetcode-cn.com/study-plan/algorithms/?progress=njjhkd2
??????簡單總結一下DFS、BFS相關的算法題：
深度優先搜索算法偽代碼：
??????一般需要建立一個 visited 數組來標記訪問過的元素。從一個節點開始，訪問它；找到它未被訪問過的后續節點，遞歸執行此算法。以下圖的二叉樹為例：訪問節點的順序依次為：A->B->C->D->E->F 類似于樹的先序遍歷。遍歷方式類似于先死磕一個方向打開缺口，再由缺口處擴散來擴大戰果，直至結束。
??????遞歸實現的偽代碼為：
廣度優先搜索算法偽代碼：
??????此算法和樹的層序遍歷基本一致。一般需要建立一個輔助隊列。搜索方法為：一圈圈擴散，從內圈開始直到最外圍，隊列用來保持內外圈的搜索順序（內圈遍歷結束才能到外圈）。以上圖的二叉樹為例：訪問節點的順序依次為：A->B->E->C->D->F 類似于樹的層序遍歷。
??????遞歸實現的偽代碼 1：
??????遞歸實現的偽代碼 2：
function bfs(graph, root) {queue = [];queue.add([root]);visit(node);while (!queue.isEmpty()) node = queue.pop();for (node in node.children()) {queue.add(node);visit(node); }??????廣度優先偽代碼 1 和 2 的差別后面在具體的問題中會講到，一般常采用偽代碼 2的寫法（即建議應該采用入隊時訪問，并且在某些情況下在出隊時訪問會造成錯誤）。
一、圖像渲染
??????題目鏈接：https://leetcode-cn.com/problems/flood-fill/
??????題目描述：有一幅以 m x n 的二維整數數組表示的圖畫 image ，其中 image[i][j] 表示該圖畫的像素值大小。
你也被給予三個整數 sr , sc 和 newColor 。你應該從像素 image[sr][sc] 開始對圖像進行 上色填充 。
為了完成 上色工作 ，從初始像素開始，記錄初始坐標的 上下左右四個方向上 像素值與初始坐標相同的相連像素點，接著再記錄這四個方向上符合條件的像素點與他們對應 四個方向上 像素值與初始坐標相同的相連像素點，……，重復該過程。將所有有記錄的像素點的顏色值改為 newColor 。
最后返回 經過上色渲染后的圖像 。
DFS：
??????其中 oldColor 表示整個二維數組中值為 oldColor 的元素需要被更改為 newColor 。**下面的算法沒有采用 visited 數組來標記訪問過的元素，因為一旦發現元素的值為 oldColor，就會改變它的值為 newColor，不會造成程序多次訪問同一個值為 oldColor 的元素，**也不會導致程序陷入循環。因此：參考上面的 DFS 模板，如果 visit() 方法不會對訪問的元素造成改變，那么就需要一個 visited 數組來進行標記，否則如本題這樣不需要 visited 數組的存在。參考算法如下：
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int oldColor=image[sr][sc];if(oldColor!=newColor)floodFill0(image,sr,sc,oldColor,newColor);return image;}public void floodFill0(int[][] image, int sr, int sc, int oldColor, int newColor) {if(sr<0||sc<0||sr>=image.length||sc>=image[0].length||image[sr][sc]!=oldColor)return; //退出條件為數組元素越界或碰到不符合要求的元素（元素值不等于 oldColor）image[sr][sc]=newColor;floodFill0(image,sr+1,sc,oldColor,newColor);floodFill0(image,sr-1,sc,oldColor,newColor);floodFill0(image,sr,sc+1,oldColor,newColor);floodFill0(image,sr,sc-1,oldColor,newColor);}??????稍微修改一下代碼，如下：
int[] x={1,0,-1,0};int[] y={0,1,0,-1};public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int oldColor=image[sr][sc];if(oldColor!=newColor)floodFill0(image,sr,sc,oldColor,newColor);return image;}public void floodFill0(int[][] image, int sr, int sc, int oldColor, int newColor) {if(sr<0||sc<0||sr>=image.length||sc>=image[0].length||image[sr][sc]!=oldColor)return;image[sr][sc]=newColor;for(int i=0;i<x.length;i++)floodFill0(image,sr+x[i],sc+y[i],oldColor,newColor);}BFS：
??????從起點開始一圈圈往外擴散。參考算法如下：
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int oldColor=image[sr][sc];if(oldColor!=newColor){int[] dx={1,0,-1,0};int[] dy={0,1,0,-1};Queue<int[]> queue=new LinkedList<>();queue.offer(new int[]{sr,sc});while(!queue.isEmpty()){int[] cell=queue.poll();int x=cell[0],y=cell[1];image[x][y]=newColor;for(int i=0;i<dx.length;i++){int mx=x+dx[i],my=y+dy[i];if(mx<0||my<0||mx>=image.length||my>=image[0].length||image[mx][my]!=oldColor){continue;}queue.offer(new int[]{mx,my});}}}return image;}上面BFS算法存在的問題：
??????按照本題描述中的示例，左上角 (0,0) 處的 1 會被添加進隊列兩次，分別由(0,1) 處的 1 添加一次，(1,0) 處的 1 再添加一次。上述算法有可能導致同一個元素入隊多次，這是我們不希望看到的。而偽代碼 2 保證了 BFS 中每個元素只能入隊一次。
修改 1：
??????偽代碼 2：在每個元素入隊時改變它的值為 newColor。參考如下：
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int oldColor=image[sr][sc];if(oldColor!=newColor){int[] dx={1,0,-1,0};int[] dy={0,1,0,-1};Queue<int[]> queue=new LinkedList<>();queue.offer(new int[]{sr,sc});image[sr][sc]=newColor;while(!queue.isEmpty()){int[] cell=queue.poll();int x=cell[0],y=cell[1];for(int i=0;i<dx.length;i++){int mx=x+dx[i],my=y+dy[i];if(mx<0||my<0||mx>=image.length||my>=image[0].length||image[mx][my]!=oldColor){continue;}queue.offer(new int[]{mx,my});image[mx][my]=newColor;}}}return image;}修改 2：
??????另一種方式即采用標記數組，這樣需要在每次入隊時標記元素為 true，修改如下：
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {boolean[][] visited=new boolean[image.length][image[0].length];int oldColor=image[sr][sc];if(oldColor!=newColor){int[] dx={1,0,-1,0};int[] dy={0,1,0,-1};Queue<int[]> queue=new LinkedList<>();queue.offer(new int[]{sr,sc});visited[sr][sc]=true;while(!queue.isEmpty()){int[] cell=queue.poll();int x=cell[0],y=cell[1];image[x][y]=newColor;for(int i=0;i<dx.length;i++){int mx=x+dx[i],my=y+dy[i];if(mx<0||my<0||mx>=image.length||my>=image[0].length||image[mx][my]!=oldColor||visited[mx][my]==true){continue;}queue.offer(new int[]{mx,my});visited[mx][my]=true;}}}return image;}??????為了防止BFS中同一個元素多次入隊的情況產生，需要在每個元素入隊時采用操作（比如修改，單純的訪問是不行的），其實更通用的方式是采用標記數組來實現。即像 DFS 那樣。
二、島嶼的最大面積
??????題目鏈接：https://leetcode-cn.com/problems/max-area-of-island/
??????題目描述：給你一個大小為 m x n 的二進制矩陣 grid 。
島嶼 是由一些相鄰的 1 (代表土地) 構成的組合，這里的「相鄰」要求兩個 1 必須在 水平或者豎直的四個方向上 相鄰。你可以假設 grid 的四個邊緣都被 0（代表水）包圍著。
島嶼的面積是島上值為 1 的單元格的數目。
計算并返回 grid 中最大的島嶼面積。如果沒有島嶼，則返回面積為 0 。
DFS：
??????本題不會對訪問的元素造成改變，所以需要 visited 數組來標記是否訪問過該元素。參考代碼如下：（當然也可以仿照上一題修改訪問過元素的值，比如將訪問過的 1 均變為 2，這樣就不需要使用 visited 數組了。缺點是會對原來的數組狀態造成破環。）
int count=0;int[] x={1,0,0,-1};int[] y={0,1,-1,0};public int maxAreaOfIsland(int[][] grid) {int re=0,m=grid.length,n=grid[0].length;boolean[][] visited=new boolean[m][n];for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1&&visited[i][j]==false){//找到每一個未被訪問過的島嶼。計算并比較其面積count=0;DFS(grid,i,j,visited);if(count>re)re=count;}}}return re;}public void DFS(int[][] grid,int i,int j,boolean[][] visited){if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]!=1||visited[i][j]==true)return;visited[i][j]=true;count++;for(int k=0;k<x.length;k++)DFS(grid,i+x[k],j+y[k],visited);}??????不帶有 visited 數組的 DFS 如下：
int count=0;int[] x={1,0,0,-1};int[] y={0,1,-1,0};public int maxAreaOfIsland(int[][] grid) {int re=0,m=grid.length,n=grid[0].length;int newValue=2;//用 2 來表示已經探查過的島嶼。for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){count=0;DFS(grid,i,j,newValue);if(count>re)re=count;}}}return re;}public void DFS(int[][] grid,int i,int j,int newValue){if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]!=1)return;grid[i][j]=newValue;count++;for(int k=0;k<x.length;k++)DFS(grid,i+x[k],j+y[k],newValue);}BFS ：
??????和上一題類似，需要在元素入隊的時候進行標記或修改操作（比如將值也置為 2 ）來防止同一個元素多次入隊；否則采用偽代碼 1 的解法會導致同一個元素多次入隊，會造成多次計數，這樣就不能得到正確結果了。
public int maxAreaOfIsland(int[][] grid) {int count=0;int[] x={1,0,0,-1};int[] y={0,1,-1,0};int re=0,m=grid.length,n=grid[0].length;boolean[][] visited=new boolean[m][n];Queue<int[]> queue=new LinkedList<>();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1&&visited[i][j]==false){count=0;queue.offer(new int[]{i,j});visited[i][j]=true;while(!queue.isEmpty()){int[] tmp=queue.poll();count++;for(int k=0;k<x.length;k++){int newX=tmp[0]+x[k],newY=tmp[1]+y[k];if(newX<0||newY<0||newX>=m||newY>=n||grid[newX][newY]!=1||visited[newX][newY]==true) continue;queue.offer(new int[]{newX,newY});visited[newX][newY]=true;}}if(count>re)re=count;}}}return re;}三、合并二叉樹
??????題目鏈接：https://leetcode-cn.com/problems/merge-two-binary-trees/
??????題目描述：給你兩棵二叉樹： root1 和 root2 。
想象一下，當你將其中一棵覆蓋到另一棵之上時，兩棵樹上的一些節點將會重疊（而另一些不會）。你需要將這兩棵樹合并成一棵新二叉樹。合并的規則是：如果兩個節點重疊，那么將這兩個節點的值相加作為合并后節點的新值；否則，不為 null 的節點將直接作為新二叉樹的節點。
返回合并后的二叉樹。
注意: 合并過程必須從兩個樹的根節點開始。
DFS：
??????參考先序遍歷，先計算當前節點的最終值，在遞歸進行左右孩子節點值的判斷，在這里需要分情況計算的。參考算法如下(這個算法完全重建了一個新的樹)：
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1!=null&&root2!=null)return new TreeNode(root1.val+root2.val,mergeTrees(root1.left,root2.left),mergeTrees(root1.right,root2.right));else if(root1==null&&root2!=null)return new TreeNode(root2.val,mergeTrees(null,root2.left),mergeTrees(null,root2.right));else if(root2==null&&root1!=null)return new TreeNode(root1.val,mergeTrees(root1.left,null),mergeTrees(root1.right,null));elsereturn null;}??????不完全重建一個新的樹的算法如下：
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1!=null&&root2!=null)return new TreeNode(root1.val+root2.val,mergeTrees(root1.left,root2.left),mergeTrees(root1.right,root2.right));else if(root1==null&&root2!=null)return root2;else if(root2==null&&root1!=null)return root1;elsereturn null;}??????或者下面這種，思路更加清晰一些，更加像樹的先序遍歷。
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {if (t1 == null) {return t2;}if (t2 == null) {return t1;}TreeNode merged = new TreeNode(t1.val + t2.val);merged.left = mergeTrees(t1.left, t2.left);merged.right = mergeTrees(t1.right, t2.right);return merged;}BFS：
??????有兩個不算問題的問題：1,兩個數中的節點入隊，如何保持相應節點的一致性？2,假設已經得到了最終樹的層序遍歷，如何恢復出一個樹？但其實問題并沒有想象中那么復雜，關鍵在于元素出隊之后要對此元素的左右孩子做判斷，來得到該位置上的最終節點。在這里只關心相應的兩個節點均不為空的情形，若任意一個節點為空，新節點置為另一個不為空的節點。另外也不需要從層序遍歷恢復出一個樹，最終的目標樹結構在每一次元素出隊時都會建立一部分，直至結束。參考算法如下：()
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {LinkedList<TreeNode> q1=new LinkedList<>();LinkedList<TreeNode> q2=new LinkedList<>();LinkedList<TreeNode> q=new LinkedList<>();if(root1!=null&&root2!=null)q.offer(new TreeNode(root1.val+root2.val));else if(root1!=null)return root1;else if(root2!=null)return root2;else return null;TreeNode re=q.peek();q1.offer(root1);q2.offer(root2);while(!q1.isEmpty()){//這里的循環條件只要 q1 或 q2 不為空即可。TreeNode a=q1.poll(),b=q2.poll(),c=q.poll();TreeNode al=a.left,ar=a.right,bl=b.left,br=b.right;if(al!=null&&bl!=null){TreeNode tmp=new TreeNode(al.val+bl.val);c.left=tmp;q.offer(tmp);q1.offer(al);q2.offer(bl);}else if(al!=null)c.left=al;else if(bl!=null)c.left=bl;if(ar!=null&&br!=null){TreeNode tmp=new TreeNode(ar.val+br.val);c.right=tmp;q.offer(c.right);q1.offer(ar);q2.offer(br);}else if(ar!=null)c.right=ar;else if(br!=null)c.right=br;}return re;}上面BFS算法存在的問題：
??????按照本題描述中的示例，左上角 (0,0) 處的 1 會被添加進隊列兩次，分別由(0,1) 處的 1 添加一次，(1,0) 處的 1 再添加一次。上述算法有可能導致同一個元素入隊多次，這是我們不希望看到的。而偽代碼 2 保證了 BFS 一定要保證一個元素只能入隊一次。
修改 1：
??????如果采用標記數組的話，需要在每次入隊時標記元素為 true，修改如下：
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {boolean[][] visited=new boolean[image.length][image[0].length];int oldColor=image[sr][sc];if(oldColor!=newColor){int[] dx={1,0,-1,0};int[] dy={0,1,0,-1};Queue<int[]> queue=new LinkedList<>();queue.offer(new int[]{sr,sc});visited[sr][sc]=true;while(!queue.isEmpty()){int[] cell=queue.poll();int x=cell[0],y=cell[1];image[x][y]=newColor;for(int i=0;i<dx.length;i++){int mx=x+dx[i],my=y+dy[i];if(mx<0||my<0||mx>=image.length||my>=image[0].length||image[mx][my]!=oldColor||visited[mx][my]==true){continue;}queue.offer(new int[]{mx,my});visited[mx][my]=true;}}}return image;}修改 2：
??????本題另一種更好的修改方式為：在每個元素入隊時改變它的值為 newColor，這樣在功能上可以做到和標記數組一樣的效果。參考如下：
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int oldColor=image[sr][sc];if(oldColor!=newColor){int[] dx={1,0,-1,0};int[] dy={0,1,0,-1};Queue<int[]> queue=new LinkedList<>();queue.offer(new int[]{sr,sc});image[sr][sc]=newColor;while(!queue.isEmpty()){int[] cell=queue.poll();int x=cell[0],y=cell[1];for(int i=0;i<dx.length;i++){int mx=x+dx[i],my=y+dy[i];if(mx<0||my<0||mx>=image.length||my>=image[0].length||image[mx][my]!=oldColor){continue;}queue.offer(new int[]{mx,my});image[mx][my]=newColor;}}}return image;}??????為了防止BFS中同一個元素多次入隊的情況產生，需要在每個元素入隊時采用操作（采用標記數組或別的方式），DFS 不會存在這樣的問題，類似于先序遍歷，它是先對元素進行操作，然后進行遞歸調用的。
四、填充每個節點的下一個右側節點指針
??????題目鏈接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
??????題目描述：給定一個 完美二叉樹 ，其所有葉子節點都在同一層，每個父節點都有兩個子節點。二叉樹定義如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 NULL。
初始狀態下，所有 next 指針都被設置為 NULL。
思路 1：
樹的層序遍歷
??????在此給出一段代碼：用來分層打印出二叉樹結點信息。如何分層是通過兩個輔助變量做到的，其中 remainingNode 表示當前層還未打印的結點數量，nextLayerN 表示下一層的結點數量。
public void printTree(){//分層打印樹節點。if(root==null)return;ArrayDeque<BinaryNode<T>> queue=new ArrayDeque<>();queue.offerLast(root);int remainingNode=1,nextLayerN=0;while(!queue.isEmpty()){BinaryNode<T> tmp=queue.pollFirst();System.out.print(tmp.element+" ");remainingNode--;if(tmp.left!=null){queue.offerLast(tmp.left);nextLayerN++;}if(tmp.right!=null){queue.offerLast(tmp.right);nextLayerN++;}if(remainingNode==0){System.out.println();remainingNode=nextLayerN;nextLayerN=0;}}}??????參考上面樹的分層打印，可得到算法如下：
public Node connect(Node root) {if(root==null)return root;LinkedList<Node> q=new LinkedList<>();q.offer(root);int remain=1,nextLayer=0;while(!q.isEmpty()){Node tmp=q.poll();remain--;if(remain>=1)//所有最右側結點的 next 值在初始化時都為 nulltmp.next=q.peek();if(tmp.left!=null){q.offer(tmp.left);nextLayer++;}if(tmp.right!=null){q.offer(tmp.right);nextLayer++;}if(remain==0){remain=nextLayer;nextLayer=0;}}return root;}思路 2：
??????在該完全二叉樹上，如果一個結點(node)存在左右結點，那么直接令 node.left.next=node.right 即可，那么 node.right.next 的值呢？如果右邊沒有結點，該值為 null；如果右邊存在結點，那么 node.right.next=node.next.left；注意：在這里我們都是在上一層構建當前層的 next 關系的。可參考算法：
public Node connect(Node root) {if(root==null)return root;Node beforeL=root,tmp;//保存上一層的最左側結點while(beforeL.left!=null){tmp=beforeL;while(tmp!=null){//構建當前層的 next 指針關系tmp.left.next=tmp.right;if(tmp.next!=null)tmp.right.next=tmp.next.left;tmp=tmp.next;}beforeL=beforeL.left;}return root;}五、01矩陣
??????題目鏈接：https://leetcode-cn.com/problems/01-matrix/
??????題目描述：給定一個由 0 和 1 組成的矩陣 mat ，請輸出一個大小相同的矩陣，其中每一個格子是 mat 中對應位置元素到最近的 0 的距離。
兩個相鄰元素間的距離為 1 。
BFS：
??????一般來講，BFS 算法可以參考樹的層序遍歷算法（分層遍歷），之前講過，BFS 可以看作是一圈圈擴散的，在本題中，初始值（初始入隊值的數量）并非只有 1 個，而是 n 個 0，但是這 n 個 0 可以抽象為一個，稱為超級源點。
??????因為它是多個源點的抽象，對它的處理方法和只有一個源點的方法沒有本質上的區別。然后需要將這些 0 周圍距離為 1 的點設置為 1，將這些 1 周圍距離為 1 的點設置為 2 ，以此類推。
??????需要注意 BFS 一定需要防止同一個元素多次入隊，用標記數組的話需要在入隊時更改元素標記，而不是在出隊時。參考算法如下：
public int[][] updateMatrix(int[][] mat) {if(mat==null||mat.length==0||mat[0].length==0)return new int[0][0];int m=mat.length,n=mat[0].length;LinkedList<int[]> queue=new LinkedList<>();boolean[][] flag=new boolean[m][n];//用來防止重復入隊int numCurr=0,numNext=0,valueCurr=0;for(int i=0;i<m;i++)//將超級源點入隊（即所有為 0 的點）for(int j=0;j<n;j++)if(mat[i][j]==0){queue.add(new int[]{i,j});flag[i][j]=true;numCurr++;}int[] tmp;int i,j; while(!queue.isEmpty()){tmp=queue.poll();numCurr--;i=tmp[0];j=tmp[1];if(j+1<n&&flag[i][j+1]==false){queue.add(new int[]{i,j+1});flag[i][j+1]=true;numNext++;}if(j-1>=0&&flag[i][j-1]==false){queue.add(new int[]{i,j-1});flag[i][j-1]=true;numNext++;}if(i+1<m&&flag[i+1][j]==false){queue.add(new int[]{i+1,j});flag[i+1][j]=true;numNext++;}if(i-1>=0&&flag[i-1][j]==false){queue.add(new int[]{i-1,j});flag[i-1][j]=true;numNext++;}mat[i][j]=valueCurr;if(numCurr==0){valueCurr++;numCurr=numNext;numNext=0;}}return mat;}??????上面代碼是在出隊的時候重新設置 mat 數組的值，為了和入隊時設置 flag 統一，將其也放在入隊的時候。順便也換一種寫法，如下：
public int[][] updateMatrix(int[][] mat) {if(mat==null||mat.length==0||mat[0].length==0)return new int[0][0];int[] x={1,0,0,-1},y={0,1,-1,0};int m=mat.length,n=mat[0].length;LinkedList<int[]> queue=new LinkedList<>();boolean[][] flag=new boolean[m][n];int numCurr=0,numNext=0;for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(mat[i][j]==0){queue.add(new int[]{i,j});flag[i][j]=true;numCurr++;}int[] tmp;int i,j; while(!queue.isEmpty()){tmp=queue.poll();numCurr--;i=tmp[0];j=tmp[1];for(int k=0;k<4;k++){int newI=i+x[k],newJ=j+y[k];if(newI>=0&&newI<m&&newJ>=0&&newJ<n&&flag[newI][newJ]==false){queue.add(new int[]{newI,newJ});numNext++;flag[newI][newJ]=true;mat[newI][newJ]=mat[i][j]+1;}}if(numCurr==0){numCurr=numNext;numNext=0;}}return mat;}DP：
??????動態規劃的做法是請參考題解。它不需要從所有為 0 的點處開始計算，而是取決于狀態轉移：dp[i][j]=Math.min(dp[i][j],dp[i-1][j]+1,dp[i+1][j]+1,dp[i][j-1]+1,dp[i][j+1]+1)，其中 dp[i][j]表示在（i，j）處的元素距離最近的 0 處的距離，即任意一個位置的距離是它本身和周圍四個格子的距離加一之間的最小值。實現的算法比較巧妙，第一次遍歷實現一半的狀態轉移（從任意位置的左上方開始），另一次遍歷實現另一半的轉臺轉移（從右下方開始），從而得到最終結果。參考算法如下：
public int[][] updateMatrix(int[][] mat) {int i,j,m=mat.length,n=mat[0].length; int[][] dp=new int[m][n];for(i=0;i<m;i++) //初始化 dp 數組，for(j=0;j<n;j++){if(mat[i][j]!=0)dp[i][j]=Integer.MAX_VALUE/2;}for(i=0;i<m;i++) //從左上方開始遍歷for(j=0;j<n;j++){if(i-1>=0)dp[i][j]=Math.min(dp[i][j],dp[i-1][j]+1);if(j-1>=0)dp[i][j]=Math.min(dp[i][j],dp[i][j-1]+1);}for(i=m-1;i>=0;i--) //從左上方開始遍歷for(j=n-1;j>=0;j--){if(i+1<m)dp[i][j]=Math.min(dp[i][j],dp[i+1][j]+1);if(j+1<n)dp[i][j]=Math.min(dp[i][j],dp[i][j+1]+1);}return dp;}六、腐爛的橘子
??????題目鏈接：https://leetcode-cn.com/problems/rotting-oranges/
??????題目描述：在給定的 m x n 網格 grid 中，每個單元格可以有以下三個值之一：
值 0 代表空單元格；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子。
每分鐘，腐爛的橘子 周圍 4 個方向上相鄰 的新鮮橘子都會腐爛。
返回 直到單元格中沒有新鮮橘子為止所必須經過的最小分鐘數。如果不可能，返回 -1 。
BFS：
??????這道題很適合用 BFS，因為從一圈到另一圈，剛好 time 加一。所以采用超級源點的 BFS，在入隊的時候更改相應的 grid 值。參考算法如下：
public int orangesRotting(int[][] grid) {int[] xa={0,1,0,-1};int[] ya={1,0,-1,0};int m=grid.length,n=grid[0].length;int[][] store=new int[m][n];LinkedList<int[]> queue=new LinkedList<>();int currT=0,num1=0;for(int i=0;i<m;i++)for(int j=0;j<n;j++){if(grid[i][j]==2){queue.add(new int[]{i,j});currT++;}else if(grid[i][j]==1)num1++;}if(num1==0) //特殊情況。return 0; int time=-1,x,y,nextT=0,xx,yy;int[] tmp;while(!queue.isEmpty()){tmp=queue.poll();x=tmp[0];y=tmp[1];currT--;for(int i=0;i<4;i++){xx=x+xa[i];yy=y+ya[i];if(xx>=0&&xx<m&&yy>=0&&yy<n&&grid[xx][yy]==1){grid[xx][yy]=2;queue.add(new int[]{xx,yy});nextT++;num1--;}}if(currT==0){time++;currT=nextT;nextT=0;}}if(num1!=0)return -1;return time;}總結
??????完。
總結
以上是生活随笔為你收集整理的LeetCode算法题7：DFS和BFS的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： LeetCode算法题6：滑动窗口*
- 下一篇： LeetCode算法题8：递归和回溯1