我們用「單位空洞」表示一個小格子是空的，「空洞」表示相鄰單位空洞結合成的大空洞。

上圖就是我們的滲透模型，黑色的表示實心的，而白色（或藍色）表示空心的，很好理解，當水從滲透塊的上方倒下來時，它會儘可能地填充聯通到最上層的空間區域，如上圖：

藍色表示被水填滿了，而白色的地方雖然是空的，但是由於其並沒有聯通到最上面，所以不能被水浸泡。

我們看，左圖和右圖的區別是什麼？

答案是左圖存在一個空洞，這個空洞聯通了最上層和最下層，所以水可以從上方滲透到下方，反過來當然也可以，而右圖的水滲透不下去的，很容易理解。

這個模擬也可以用來解釋導體的導電性能，只要將水流換成電流，空洞變成可以自由移動載流子的地方即可。

好，我們想想這個模型和Union Find數據結構有什麼關係。

我們發現：當兩個單位空洞接觸的時候，兩個單位空洞所在的集合就會合併成同一集合。

空洞就像水滴一樣，當兩個空洞接觸的時候，哪怕僅僅的接觸一點點，兩個空洞就會合併成一個更大的空洞。

這不正是UnionFind結構所能提供給我們的功能嗎？

假如現在在（4，3）和（4，4）位置的兩個方塊都是空的，那麼我們只需：

union（（4，3），（4，4））即可。

而怎麼檢測這個方塊是否滲水呢？

這裡面有一個小技巧，我們發現不管最上層開多少口，它們都相當於連接到第一層上方的空間，也就是說石頭的上方是全空著的，下方也一樣，我們引入兩個元素：Bottom 和Top來表示石頭外的空間，如圖：

注意，它們表示的是石頭外面的空間，而不是石頭裡面的，所以最上層的所有空洞都應該連接到Top元素，最下層的單位空洞則連接到Bottom元素。

那麼如何檢測一個石頭是否滲水呢？

當然就是檢測Bottom元素和Top元素是否連接在一起了！

也就是檢驗 connected(Bottom, Top) 的真假！（不明白的同學看上一節UnionFind）。

而且僅僅是做計算未免太無聊，我們希望可以把它圖形化，讓滲透的情況呈現在我們眼前。

好，打開Eclipse開始戰鬥：

首先創建一個工程，把我們上節課做好的QuickUnionUF的類放進去，作為我們的API。

新建一個Percolation, 然後讓它自己繼承Canvas。

Canvas是Java自帶的繪圖工具，繼承了它的類，自己就變成了一個畫板，可以將自己的一些元素畫到自己身上，但是畫板還需要一個容器，也就是窗口，我們將用JFrame作為窗口。

首先Percolation需要有一個Constructor，我們用它來確定滲透塊的尺寸，在Constructor里接受一個參數n，然後創建一個n*n的二維數組來表示石塊的每個單元，這個數組需要是Boolean型的，因為我們只需表示「打開」和「關閉」兩個量，我們用true表示打開，false表示關閉。

聲明幾個變數，分別是：

滲透塊的尺寸：size； 進行集合合併操作的UF；存儲網格開閉信息的二維數組：grid；

窗口的寬和高。

Constructor:

19-21：用作尺寸的n需要大於一，如果小於一，我們拋出一個錯誤。

22-24：將剛才的幾個量初始化，注意UF的初始化，我們讓UnionFind有size*size+2個元素，為什麼呢？因為要有Top和Bottom！我們默認Top是第一個，Bottom是最後一個，中間的就是我們的網格。

所以對於尺寸為5的滲透塊，第三排第二列的元素對應於UF的位置是？

只需：5*（3-1）+2 = 12，也就是說，UF[12]對應網格的（2，3）。

同理: UF[1]對應（1，1），UF[0]對應Top，UF[26]對應Bottom。

創建兩個顏色變數，分別作為實心和空心的顏色。

在main方法里創建一個Percolation的實例，然後創建一個JFrame實例，讓percolation（繼承了canvas）添加到frame裡面（39行），剩下的模仿就好，不是本講重點，相關信息可去查閱Java官方文檔的關於JFrame的知識。

為了讓percolation實例自己能把自己畫出來，我們需要一個方法：paintBrick();(畫磚頭，名字隨便起)，讓它來程序話的將二維數組的信息轉化成生動的圖像。

很簡單的雙層循環，分別循環橫坐標和縱坐標，然後如果當前網格為true（打開狀態），那就在該位置畫上一個正方形，正方形的寬度當然是總寬度除以size了，但是我們為了讓方塊更明顯，我們稍稍的縮小方塊的大小，乘個0.9，這樣方塊之間就用空隙了，看起來比較好看。

接下來，我們需要一個open（）方法，用來打開特定位置的單位塊。

48：檢查指數是否在規定範圍。

49：廢話不說，讓它等於true。

50-52：如果在第一行，讓它和top進行連接。

53-55：檢查相鄰元素是否也是空的，上下左右檢查四次，如果空的，連接當前的和它相鄰的空單位塊。

56-58：如果在最後一行，讓它和bottom進行連接。

剛剛用到的，檢查腳標是否在範圍內。

分四種情況，用direction來控制情況，第二層if判斷該方位的相鄰元素是否存在，第三層if用來判斷是否打開，如果打開，連接。

判斷top與bottom是否連接，如果連接，則滲透成功。

增加一個自由變數，用來記錄已經打開的單位空洞個數，每次打開，都讓它加一。

好，這個就是核心了，我們用它來不斷地打開新單位塊，然後更新數據，檢查是否滲漏，如果沒滲漏，繼續打開新單位塊，直到滲透為止，然後輸出打開的面積與總面積的比，也就是：

numOfopen/n^2。

我們看，每次循環，我們都會讓delta增加一段時間，這段時間的單位是什麼？數據的次數，為什麼呢？

我們通過System.nanoTIME（）獲取的數據是以納秒為單位的，那麼我們除以10^9後就是以秒為單位，再乘以一個amountOfTicks，單位就會變成：

1/amountOfTicks*秒。

也就是說，假如amountOfTicks是60，那麼當delta = 1的時候，表示過去了1/60秒，也就是說每當delta>=1時，我們就執行一次140-163的if語句，然後執行delta--，讓它回到原來的值，如此往複，既每秒運行60次這個if語句。

這裡面涉及到BufferedStrategy，只需照做就行，不是本課重點。

好，運行一下程序：

發現概率是0.6左右，我們查一下：

我們發現概率的門檻是0.593，也就是說，當打開的面積佔比超過0.593時，滲透快就幾乎是可滲透的！

源碼鏈接:

https://pan.baidu.com/s/1Uz-rjEXYHSw1zbj_gIDfRg

推薦閱讀：