通吃島嶼問題

總結：本節使用bfs與dfs通吃島嶼問題，後面還會有更多類似文章，期待留言交流！

1.島嶼問題

在秋招及實習期間發現島嶼問題在面試中會被經常問到，本節來把leetcode上的所有島嶼問題通吃一遍。

本節涉及的題目依次如下：

200.島嶼數量

https://leetcode-cn.com/problems/number-of-islands/

694.不同島嶼的個數

https://leetcode-cn.com/problems/number-of-distinct-islands/

711.不同島嶼的個數II

https://leetcode-cn.com/problems/number-of-distinct-islands-II/

695.島嶼的最大面積

https://leetcode-cn.com/problems/max-area-of-island/

463.島嶼的周長

https://leetcode-cn.com/problems/island-perimeter/

2.邏輯彙總

針對以上題目，先分析不同題目的差別，随後給出相應的模闆的解決這種問題，拿最簡單的第200題來說。

第200題目如下：

給你一個由 '1'（陸地）和 '0'（水）組成的的二維網格，請你計算網格中島嶼的數量。

島嶼總是被水包圍，并且每座島嶼隻能由水準方向或豎直方向上相鄰的陸地連接配接形成。

此外，你可以假設該網格的四條邊均被水包圍。

示例 1:

輸入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
輸出: 1

複制

解法描述：針對這種問題我們可以采用dfs/bfs來解決，當然也可以才uf算法來解決，本節我們主要來套用dfs/bfs。

dfs算法與bfs算法不懂的就不多闡述了，本節的所有知識體系是建立在你知道該算法的基礎之上，進行最佳實踐。

下面給出一個bfs架構：

class Solution {
private:
  int direct[4][2] = {
      {0, 1},
      {0, -1},
      {1, 0},
      {-1, 0}};
  vector<vector<bool>> visited;
  int n, m;

public:
  // bfs
  int numIslands(vector<vector<char>> &grid)
  {
    n = grid.size();
    if (n == 0)
    {
      return 0;
    }
    m = grid[0].size();

    visited = vector<vector<bool>>(n, vector<bool>(m, false));
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < m; j++)
      {
        if (grid[i][j] == '1' && !visited[i][j]) // 是小島
        {
          visited[i][j] = true;
          // bfs邏輯
          ans++; // 島嶼數量
        } 
      }
    }
    return ans;
  }
  bool inArea(int x, int y)
  {
    return x >= 0 && x < n && y >= 0 && y < m;
  }
};

複制

相信上面代碼一看就會，值得說明的一點使用了visit來判斷是否再次通路，用來标記已經通路過的點。

下來就是bfs的主要邏輯，無非就是一個隊列，然後進出隊列即可，明确以下幾點：

何時出隊列
何時進隊列

出隊列沒啥好說的，隻有進去的出就完事了，進隊列那就是滿足特定條件，這裡特定條件有：

新節點(上下左右四個方向的節點)未通路過
新節點是島
新節點未超出邊界

接下來就是中間bfs的邏輯：

queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty())
{
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    for (int k = 0; k < 4; k++)
    {
      int newX = x + direct[k][0];
      int newY = y + direct[k][1];
      if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == '1')
      {
        q.push({newX, newY});
        visited[newX][newY] = true;
      }
    }
}

複制

簡單吧~

随後，給大家一個dfs架構，bfs外殼不變，改掉内部的bfs部分即可。

與dfs架構不同在于兩點：

visited[i][j] = true dfs内部處理
bfs邏輯替換未dfs邏輯

// 其他部分不變
for (int i = 0; i < n; i++)
{
  for (int j = 0; j < m; j++)
  {
    if (grid[i][j] == '1' && !visited[i][j])
    {
      int area = dfs(grid, i, j); // 這裡變了 
      ans++;
    }
  }
}
// 其他部分不變

複制

dfs邏輯我們要明白，什麼時候遞歸終止，如何防止死遞歸。

防止死遞歸，前面有個visited即可防止
遞歸終止：新節點不在網格區域或者在網格區域但是被通路過，再或者不是島。

int dfs(vector<vector<char>> &grid, int x, int y)
{
    if (!inArea(x, y) || (inArea(x, y) && visited[x][y]) || grid[x][y] == '0')
      return 0;
    int area = 1; // (x,y)
    visited[x][y] = true;
    for (int i = 0; i < 4; i++)
    {
      int newX = x + direct[i][0];
      int newY = y + direct[i][1];
      area += dfs(grid, newX, newY);
    }
    return area;
}

複制

上述兩個代碼完整版：

class Solution
{
private:
  int direct[4][2] = {
      {0, 1},
      {0, -1},
      {1, 0},
      {-1, 0}};
  vector<vector<bool>> visited;
  int n, m;

public:
  // bfs
  int numIslands(vector<vector<char>> &grid)
  {
    n = grid.size();
    if (n == 0)
    {
      return 0;
    }
    m = grid[0].size();

    visited = vector<vector<bool>>(n, vector<bool>(m, false));
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < m; j++)
      {
        if (grid[i][j] == '1' && !visited[i][j])
        {
          visited[i][j] = true;
          queue<pair<int, int>> q;
          q.push({i, j});
          while (!q.empty())
          {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int k = 0; k < 4; k++)
            {
              int newX = x + direct[k][0];
              int newY = y + direct[k][1];
              if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == '1')
              {
                q.push({newX, newY});
                visited[newX][newY] = true;
              }
            }
          }
          ans++;
        }
      }
    }
    return ans;
  }
  bool inArea(int x, int y)
  {
    return x >= 0 && x < n && y >= 0 && y < m;
  }
};

複制

class Solution
{
private:
  int direct[4][2] = {
      {0, 1},
      {0, -1},
      {1, 0},
      {-1, 0}};
  vector<vector<bool>> visited;
  int n, m;

public:
  int numIslands(vector<vector<char>> &grid)
  {
    n = grid.size();
    if (n == 0)
    {
      return 0;
    }
    m = grid[0].size();

    visited = vector<vector<bool>>(n, vector<bool>(m, false));

    int ans = 0;
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < m; j++)
      {
        if (grid[i][j] == '1' && !visited[i][j])
        {
          int area = dfs(grid, i, j);
          ans++;
        }
      }
    }
    return ans;
  }

  int dfs(vector<vector<char>> &grid, int x, int y)
  {
    if (!inArea(x, y) || (inArea(x, y) && visited[x][y]) || grid[x][y] == '0')
      return 0;
    int area = 1; // (x,y)
    visited[x][y] = true;
    for (int i = 0; i < 4; i++)
    {
      int newX = x + direct[i][0];
      int newY = y + direct[i][1];
      area += dfs(grid, newX, newY);
    }
    return area;
  }
  bool inArea(int x, int y)
  {
    return x >= 0 && x < n && y >= 0 && y < m;
  }
};

複制

好了，明白上述bfs與dfs操作，我們可以分分鐘感到665.島嶼的最大面積與463.島嶼的周長。

695.島嶼的最大面積

這道題是上面那道題的變種，上面是求有多少個島嶼，這道題是所有島嶼面積中最大的，那簡單啊，直接統計面積，取max就行了，這也是為什麼上面那道題dfs算法架構我傳回值是int，并且裡面我也計算了area，bfs架構中添加下面三行即可，其他不變。

if (grid[i][j] == 1 && !visited[i][j])
{
  // todo
  int area = 1; // this line
  while (!q.empty())
  {
 // todo
    for (int k = 0; k < 4; k++)
    {
      // todo
      if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == 1)
      {
        area++; // this line
      }
    }
  }
  ans = max(ans, area); // this line
}

複制

dfs代碼改的更少：隻需要更改this line即可。

if (grid[i][j] == 1 && !visited[i][j])
{
  int area = dfs(grid, i, j);
  ans = max(ans, area);  // this line
}

複制

463.島嶼的周長

這道題有點意思，圍繞的周長，其實可以兩句話概括：

島嶼變水域或邊界加1
水域之間不變

bfs實作：隻需要修改下面幾行即可。

if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == 1)
{
    q.push({newX, newY});
    visited[newX][newY] = true;
}
else if (!inArea(newX, newY) || grid[newX][newY] == 0) // this line
{
    ans++;
}

複制

dfs實作：切記area有1變為0，因為前面計算的是面積，1代表的是目前節點，而這裡改為0是因為我們計算周長，原理都不一樣，一定要好好體會。

除此之外修改之前的終止條件未下面兩行即可。

島嶼變水域或邊界加1

傳回1表示超出邊界或者進入水域。

int dfs(vector<vector<int>> &grid, int x, int y)
{
    // 島嶼變水域或邊界 加1 
    if (!inArea(x, y) || grid[x][y] == 0) return 1;
    if (inArea(x, y) && visited[x][y]) return 0;
    // 水域之間不變
    int area = 0;
    // 其餘不變
}

複制

最後，就是兩個比較麻煩的題目。

694.不同島嶼的個數

複制

這兩個表示不同的島嶼。

711.不同島嶼的個數II

複制

這兩個表示相同的島嶼。

711是694的提升版，進行旋轉、對稱之後的島嶼是一樣的，那麼就是相同島嶼，而694隻認為平移相同才算相同的島嶼。

先看694題解法。我們重點就是判重就行了，需要使用一種方式來表達不同島嶼。這裡采用坐标相對偏移來保證這一點。

例如：

11
1

複制

假設我們周遊方式是bfs，并且先下後右，那麼依次的偏移：

[[0,0],[1,0],[0,1]]

複制

同理，得到

1
11

複制

為：

[[0,0],[1,0],[1,1]]

複制

那麼它們隻要形狀不同，必定這個結果是不同的，我們可以采用兩種形式刻畫相對偏移：

比較數組結構

[[0,0],[1,0],[0,1]]是否等于[[0,0],[1,0],[1,1]]

複制

比較字元串結構

0_0_1_0_0_1_是否等于0_0_1_0_1_1_

複制

可以明顯發現第二種方法是比較優的。

是否等于我們可以用一個set刻畫，這樣隻要往裡面插入永遠是不一樣的，最後傳回set的大小就是不同島嶼個數，接下來我們按照這兩種方式來進行闡述。

數組結構的bfs

visited[i][j] = true;
queue<pair<int, int>> q;
q.push({i, j});
vector<pair<int, int>> axis; // this line 沒有放入[0,0]坐标
while (!q.empty())
{
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    for (int k = 0; k < 4; k++)
    {
      int newX = x + direct[k][0];
      int newY = y + direct[k][1];
      if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == 1)
      {
        q.push({newX, newY});
        visited[newX][newY] = true; 
        axis.push_back({newX - i, newY - j}); // this line
      }
    }
}
s.insert(axis); // this line

複制

隻需要改動最上面架構的三行就可以實作。

數組結構的dfs

for (int i = 0; i < n; i++)
{
  for (int j = 0; j < m; j++)
  {
    if (grid[i][j] == 1 && !visited[i][j])
    {
      vector<pair<int, int>> axis; // this line
      dfs(grid, i, j, axis); // this line
      s.insert(axis); // this line
    }
  }
}

複制

dfs中修改：

void dfs(vector<vector<int>> &grid, int x, int y, vector<pair<int, int>>& axis) {
    if (!inArea(x, y) || (inArea(x, y) && visited[x][y]) || grid[x][y] == 0) {
      return;
    }
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
      int newX = x + direct[i][0];
      int newY = y + direct[i][1];
      axis.push_back({newX-x,newY-y}); // this line
      dfs(grid, newX, newY, axis);
    }
}

複制

可以看到标記this line的賊少。

字元串結構的bfs與dfs

同理，把上述的

axis.push_back({newX-x,newY-y});

改為下面一行就可以實作字元串結構的bfs。

encode += to_string(newX - i)  + "_" + to_string(newY - j) + "_";

複制

接下來，我們來看一下，最後一道題711，711是在694的基礎上進行演化，允許旋轉、對稱作為一樣的圖行，我們隻需要寫一個正規化函數，得到島嶼的坐标數組後，進行正規化處理，放入set即可。

關鍵點便是正規化函數如何實作：

我們知道：一個點[x,y]對稱可以得到[x,-y],[-x,y],[-x,-y]，交換x與y，得到：[y,x],[y,-x],[-y,x],[-y,-x]。

是以我們得到一個結論：得到一個島嶼對應的數組，該數組可以找到8種結構(包含自身)。

為了統一，由于順序不同引起，還會有多種結果，是以我們需要通過排序，這樣每次一個島嶼的形狀(旋轉、對稱)正規化後得到的一個正規化結果一定是一樣的。

bfs實作：

set<vector<pair<int, int>>> s;
visited = vector<vector<bool>>(n, vector<bool>(m, false));
for (int i = 0; i < n; i++)
{
  for (int j = 0; j < m; j++)
  {
    if (grid[i][j] == 1 && !visited[i][j])
    {
      visited[i][j] = true;
      queue<pair<int, int>> q;
      q.push({i, j});
      vector<pair<int, int>> axis{{i,j}};
      while (!q.empty())
      {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++)
        {
          int newX = x + direct[k][0];
          int newY = y + direct[k][1];
          if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == 1)
          {
            q.push({newX, newY});
            visited[newX][newY] = true;
            axis.push_back({newX,newY}); // this line
          }
        }
      }
      s.insert(Normalize(axis)); // this line
    }
  }
}

複制

dfs實作：

for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
    if (grid[i][j] == 1 && !visited[i][j]) {
      vector<pair<int, int>> axis;
      dfs(grid, i, j, axis);
      s.insert(Normalize(axis)); // this line
    }
  }
}
void dfs(vector<vector<int>> &grid, int x, int y, vector<pair<int, int>>& axis) {
    if (!inArea(x, y) || (inArea(x, y) && visited[x][y]) || grid[x][y] == 0) {
      return;
    }
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
      int newX = x + direct[i][0];
      int newY = y + direct[i][1];
      axis.push_back({newX,newY}); // this line
      dfs(grid, newX, newY, axis);
    }
}

複制

結構寫好了，我們來寫正規化函數：

所有想說的都在前面提到了，配上注釋看。

vector<pair<int,int>> Normalize(const vector<pair<int,int>>& rawShape) {
    vector<vector<pair<int,int>>> shapes(8); // 旋轉+鏡像

    // 得到每一種形狀
    for (auto& sp : rawShape) {
        int x = sp.first;
        int y = sp.second;
        // 鏡像
        shapes[0].push_back({x,y});
        shapes[1].push_back({x,-y});
        shapes[2].push_back({-x,y});
        shapes[3].push_back({-x,-y});
        // 旋轉
        shapes[4].push_back({y, x});
        shapes[5].push_back({y,-x});
        shapes[6].push_back({-y,x});
        shapes[7].push_back({-y,-x});
    }

    for (auto& sp : shapes) {
        // 每種shape進行排序
        sort(sp.begin(), sp.end());
        // 得到這種shape的相對坐标
        for (int i=rawShape.size()-1;i>=0;i--) {
            sp[i].first -= sp[0].first;
            sp[i].second -= sp[0].second;
        }
    }

    // 所有相對坐标的不同shape進行排序
    sort(shapes.begin(), shapes.end());
    return shapes[0]; // 随便取一種
}

複制

總結：本節使用bfs與dfs通吃島嶼問題，後面還會有更多類似文章，期待留言交流！

通吃島嶼問題通吃島嶼問題

通吃島嶼問題

1.島嶼問題

2.邏輯彙總