文章目錄
- 1.算法簡介
- 2.題目概述
- 3.算法原理
- 4.代碼分析
1.算法簡介
這個算法是關于我們的floodfill的相關的問題，這個算法其實從名字就可以看出來：洪水灌溉，其實這個算法的過程就和他的名字非常相似，下面的這個圖就生動的展示了這個算法的相關原理；
其實這個就是想要找到性質相同的聯通快：使用下面的這個圖形里面的數據作為例子，第二行第二列的這個數據是5，當洪水從左上角進來的時候，你可以把這個區域想象成為一個梯田，當洪水來臨的時候，左上角的這個-1，-2，-3都會被淹掉，我們可以把這個想象成為地理上面學習的這個等高線之類的，地勢低的位置肯定是先被淹掉，這個應該是很容易理解的；
同理，當這個洪水從右上方來臨的時候，負數的更小，對應的這個區域肯定會被淹沒，這個是顯然的；
大致就是這個過程，為什么這個和我們的bfs相關呢？因為我們確定這個被淹沒的區域的時候，思路就是從他身邊的進行比較，如果高的話，自己肯定機會唄淹沒了，但是如果對方低的話，對方就會被淹掉，通過不斷的這個遍歷搜索的過程，最終確定想要的結果；
這個思路比較簡單，但是過程很抽象，我們通過leetcode上面的一個具體的題目進行說明；
2.題目概述
下面的這個就是關于洪水灌溉的題目：leetcode773圖像渲染；
解釋一下上面的這個示例想要表達的意思把：我覺得相對于上面的大段的文字，這個示例圖示會更加容易理解一些，這個示例的意思就是給你一個sr,sc,color，這個sr和sc表示的就是需要被渲染的搜索起點，我們從這個位置開始，這個color就是把這個相關的符合條件的點全部染成這個color對應的顏色；
看這個（1,1）表示的就是第二行的第二列對應的元素，這個很好理解，這個元素就是1，而我們需要渲染的這個顏色就是2，兩個是不一樣的，因此這個需要我們進行操作，如果兩個的顏色是一樣的，這個過程就是多余的，因此我們寫代碼的時候需要進行判斷一下；
周圍的這個點必須是直接相鄰的，可以是sr,sc的鄰居，也可以是他的鄰居的鄰居，大家可以理解我的意思吧，總之這個區域需要是聯通的，不可以是分散的孤立的，這個是重點；
3.算法原理
理解上面的這個題目對應的示例之后，接下來開始進行這個算法的原理的分析：
下面的這個是一個新的圖，進行這個算法的原理的說明，sr,sc還是（1,1），color=2，說明以這個（1,1）作為起點，這個color就是我們想要把這個相關的點染成的顏色為2；
下面的這個是第一步，現對于這個（1，1)上下左右的位置進行判斷：發現了兩個目標，就是圖里面的斜線經過的兩個點的位置；
下面的是新的一輪的搜索，這個時候是以上面的兩個作為基礎，繼續操作，這個時候又找到了三個符合條件的數據點的坐標
下面的這個是：在上一步的基礎上面繼續操作，這個時候找到了兩個符合條件的坐標；
接下來輪到第四層的時候，發現第三層的這個元素的周圍已經沒有其他的元素的，因此這個時候我們的這個廣度優先遍歷的過程就結束了；
4.代碼分析
- 剛開始的這個dx,dy數組是后面進行上下左右的遍歷的時候用到的，下面的這個圖片會進行說明；
- prev就是題目給定的這個位置的元素值，我們需要判斷他和color是不是一樣的，如果是有一樣的，接下來就不需要進行判斷了；
- m,n的定義主要是為了越界問題的定義，我們首先把這個sr,sc放到這個隊列里面去；
- 循環里面，我們取出來這個對首的元素，因為這個隊列里面的每一個元素都是一個二維的數組，我們使用這個a,b記錄他對應的橫縱坐標即可，然后進行對應的顏色的渲染；
- 里面的這個for循環就是上下左右進行判斷的，符合條件的進行染色，最后返回處理之后的image即可；
class Solution {int[] dx={0,0,1,-1};int[] dy={1,-1,0,0};public int[][] floodFill(int[][] image, int sr, int sc, int color) {int prev=image[sr][sc];if(prev==color) return image;int m=image.length,n=image[0].length;Queue<int[]> q=new LinkedList<>();q.add(new int[]{sr,sc});while(!q.isEmpty()){int[] t=q.poll();int a=t[0],b=t[1];image[a][b]=color;for(int i=0;i<4;i++){int x=a+dx[i],y=b+dy[i];if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==prev){q.add(new int[]{x,y});}}}return image;}
}
下面的這個圖是說明我們的上下左右的坐標是如何表示的：
上下左右，發現這個點的坐標就是-1，+1的操作，因此我們定義了這個dx,dy數組，在上面的這個代碼的for循環里面，我們使用這個數組相當于是完成了對于這個已知點的周圍的幾個點的判斷，這個很方便，大家可以借鑒一下；
操作，因此我們定義了這個dx,dy數組，在上面的這個代碼的for循環里面，我們使用這個數組相當于是完成了對于這個已知點的周圍的幾個點的判斷，這個很方便，大家可以借鑒一下；
