Number of Islands

題目描述

Given a 2d grid map of '1' s (land) and '0' s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:

11110
11010
11000
00000

Answer: 1
Example 2:

11000
11000
00100
00011

Answer: 3

解題思路

拿到題目，如果對數(shù)據(jù)結(jié)構(gòu)——“圖”的內(nèi)容比較熟悉，很容易就能想到用DFS或BFS來解決。通過這兩種途徑解決該問題相對不太難币砂，并且網(wǎng)上有大量講解，所以我不再贅述裹虫。今天要說的是種新的算法（對我來說）——union-find 算法（見《算法》1.5節(jié)）恐锦。

union-find 算法簡介

顧名思義，union即合并役听，find為查找颓鲜，核心就在這兩部分表窘。完整的算法的行為就是通過不斷的find出某兩個元素分別所屬的集合，判斷他們是否是同一個甜滨，然后將不屬于同一集合的兩個元素union到同一個集合中乐严。
那它到底是用來干嘛的呢？
嗯...書上說...它主要是用來解決動態(tài)連通性問題的衣摩。如果你不知道什么是動態(tài)連通性昂验，還是請你查閱書籍，我不覺得自己有能力解釋的比書上更好艾扮，起碼在現(xiàn)階段...
好在要解決今天這個問題既琴，你還不需要明白那些復(fù)雜的東西，讓我們進(jìn)入正題栏渺。

UF 數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)（C++）

抽象圖

在此之前我們先來分析下題目：
將所給二維數(shù)組抽象成一個圖（如上）呛梆，標(biāo)記 1 的為陸地，標(biāo)記為 0 的是水域磕诊，相鄰的陸地連接在一起成為島嶼，即圖中的連通分量纹腌。所以本題就轉(zhuǎn)換成為：求所給圖的連通分量總數(shù)霎终。

class UF {
public:    
  int count = 0; //用來記錄總的連通分量數(shù)目   
  int *id;     //數(shù)組的元素對應(yīng)各頂點，存儲的內(nèi)容為它自身所屬所屬連通分量的名稱  
  //這里不太容易理解升薯，我打個比方：  
  //一群互不相識的小孩兒參加夏令營莱褒，老師把他們分成多組，每組選出一人為隊長涎劈，并要求按組排隊集合广凸。
  //集合站隊時，隊長站在最前方蛛枚，其他人通過辨認(rèn)自己的隊長來選擇自己的隊伍谅海。
  //理論上只要每人都記住隊長的樣子就能站好隊伍，但也并非必須如此蹦浦。
  //也許在第一次排隊的時候小孩兒B沒記住自己的隊長扭吁，但他記住了自己前面的小朋友A，那只要A站對了位置盲镶，他就能跟著A站到正確的位置了侥袜。
  //這里id數(shù)組的元素就像是一個小孩兒，它所存儲的就是自己記住的那個跟自己在同一隊的小伙伴的樣子溉贿，當(dāng)然這個人可能是隊長枫吧，也可能是其他任何一個同隊的人 。    
  
//構(gòu)造函數(shù)    
  UF(int m, int n, vector<vector<char>>& grid) {  
    for (int i = 0; i < m; i++) {           
      for (int j = 0; j < n; j++) {                
        if (grid[i][j] == '1') count++;  
        //初始化count值的時候宇色，我們假設(shè)每塊陸地起初都是孤立的九杂，所以有多少塊陸地闽寡，就有多少個連通分量
      }       
    }        
    int a[m*n];        
    id = a;        
    for (int i = 0; i < m * n; i++) {            
      id[i] = i;  
      //如上面所假設(shè)的，每塊陸地都是孤立的（換成排隊即指每個孩子除了自己誰都不認(rèn)識尼酿，所以他們各自為營）爷狈，所以自己的id里存儲的就是自己的下標(biāo)       
    }   
  }        

  //尋找p所屬的連通分量的名稱（換成排隊即尋找p小孩兒的隊長）    
  int find(int p) {           
    while (p != id[p]) {             
      id[p] = id[id[p]];            
      p = id[p];       
    }        
    return p;   
  }  
  //當(dāng)然隊長只需要認(rèn)識自己，站在原地不動就好裳擎，所以如果id[p]==p涎永，那他就是隊長，否則就說明他（id[p]）只是P小孩記住的那個同隊的小伙伴鹿响。
  //為了找到隊長羡微，需要再問id[p]小朋友他記住的那個同隊的小伙伴（id[id[p]]）是不是隊長了。
  //一直這么問下去惶我，總會找到隊長本人的（畢竟不聽話的搗蛋鬼只是少數(shù)呀）        

  //判斷p妈倔，q是否屬于同一連通分量（即兩塊陸地是否相連...或者兩個小孩是不是同一隊的）    
  bool isConnected(int p, int q) {         
    int pRoot = find(p); //p的隊長        
    int qRoot = find(q); //q的隊長        
    if (pRoot != qRoot)           
      return false; //若兩個隊長不是同一個人，則他們不同隊        
    else           
      return true; //否則同隊    
  }        

  //合并p绸贡，q所屬的兩個連通分量（或者說把兩隊小孩組成一隊）    
  void myUnion(int p, int q) {        
    int pRoot = find(p);        
    int qRoot = find(q);        
    if (pRoot == qRoot) return;        
    id[pRoot] = qRoot; //讓p的隊長（pRoot）認(rèn)q的隊長（qRoot）為自己的隊長盯蝴，就是說pRoot的職務(wù)被罷免了...        
    count--; //結(jié)果當(dāng)然是總隊伍數(shù)少一個～   
  }
};

利用 UF 設(shè)計算法求島嶼數(shù)

實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的時候，我們假設(shè)一開始每塊陸地是孤立的听怕，就是把每塊陸地都當(dāng)成一個島嶼捧挺。這顯然不符合題意，現(xiàn)在我們要做的就是找出所有相連的陸地尿瞭，并把他們union到一起闽烙，直到所有相連的陸地都被包含在同一個島嶼中為止。

//求總的島嶼數(shù)（即其中的連通分量總數(shù)）
int numIslands(vector<vector<char>>& grid) {    
  if (grid.size() == 0 || grid[0].size() == 0)       
    return 0;  //如果沒有陸地声搁，當(dāng)然就沒有島嶼...    

  int m = (int)grid.size(), n = (int)grid[0].size();    
  UF uf = UF(m, n, grid);      

  //從上向下黑竞，從左向右地遍歷整個圖，遇到陸地疏旨，就把它和自己周圍的（上下左右四個方向）陸地or島嶼合并
  for (int i = 0; i < m; i++) {        
    for (int j = 0; j < n; j++) {            
      if (grid[i][j] == '0') continue;            
      int p = i * n + j;            
      int q;            
      if (i < m - 1 && grid[i + 1][j] == '1') { //右邊相鄰                
        q = p + n;                
        uf.myUnion(p, q);           
      }            
      if (j < n - 1 && grid[i][j + 1] == '1') { //下邊相鄰                
        q = p + 1;                
        uf.myUnion(p, q);           
      }       
    }   
  }  
  //由于我們是按照從上向下很魂，從左向右的順序進(jìn)行遍歷，所以當(dāng)我們遍歷到某頂點時充石，它上面和左邊的頂點一定已經(jīng)遍歷過了
  //所以事實上我們只需要對每個頂點作右和下方的判斷即可      

  return uf.count; 
  //每次union都會count--莫换，所以當(dāng)完整遍歷整個圖之后，count就是我們需要的島嶼數(shù)量了
}

??int main(int argc, const char * argv[]) {    
  vector<vector<char>> grid;    
  string s[4] = {"11000", "11000", "00100", "00011"};    
  int i = 0;    while (i < 4) {        
    vector<char> line(s[i].begin(), s[i].begin() + s[i].length());        
    grid.push_back(line);        
    ++i;   
  }    
  cout << numIslands(grid) << endl;    
  return 0;
}

總結(jié)

一開始我只是看到說union-find算法可以解決島嶼問題骤铃，剛好手邊的《算法》書里有詳細(xì)講解拉岁，就想學(xué)習(xí)后自己試著實現(xiàn)一下《枧溃可當(dāng)我花了近兩個小時終于似乎學(xué)會了這個算法喊暖，打算小試牛刀的時候，卻完全找不到用它解決島嶼問題的思路撕瞧。最終我還是放棄了陵叽，到 LeetCode 上查看了大佬的 solution狞尔，并醍醐灌頂，自嘆不如巩掺。大佬是用 Java 實現(xiàn)的偏序，看過之后為加深印象，也為溫習(xí) C++胖替，我決定重新實現(xiàn)一下研儒，便有了這篇文章。寫過之后我發(fā)現(xiàn)自己對這個算法的理解更深了一層独令，希望能幫助更多的朋友端朵。