leetcode：694. 不同岛屿的数量（会员题）
lintcode：860 · 不同岛屿的个数

题目

给定一个由 0 和 1 组成的非空的二维网格，一个岛屿是指四个方向（包括横向和纵向）都相连的一组 1（1 表示陆地）。你可以假设网格的四个边缘都被水包围。

找出所有不同的岛屿的个数。如果一个岛屿与另一个岛屿形状相同（不考虑旋转和翻折），我们认为这两个岛屿是相同的。

注意：

11
1

和

 1
11

是不同的岛屿，因为我们不考虑旋转和翻折。

示例：

输入:
  [
    [1,1,0,0,1],
    [1,0,0,0,0],
    [1,1,0,0,1],
    [0,1,0,1,1]
  ]
输出: 3
解释: 
  11   1    1
  1        11   
  11
   1

输入: 
  [
    [1,1,0,0,0],
    [1,1,0,0,0],
    [0,0,0,1,1],
    [0,0,0,1,1]
  ]
输出: 1

解答 & 代码

本题和[中等] 200. 岛屿数量的区别就是，本题统计的是不同的岛屿的数量。
因此，可以考虑用哈希表记录不同形状的岛屿，最终哈希表的大小就是不同岛屿的数量。

问题就转换为：如何记录岛屿的形状？

可以将岛屿转换成字符串，即序列化。
在 dfs 遍历岛屿的时候，记录遍历的方向（路径），来序列化岛屿形状

具体的，'u,', 'd,', 'l,', 'r,' 分别代表向上、向下、向左、向右，'-u,', '-d,', '-l,', '-r,' 分别代表撤销向上、撤销向下、撤销向左、撤销向右

class Solution {
private:
  void dfs(vector<vector<int>>& grid, int row, int col, string& path, char direction)
  {
      int rows = grid.size();
      int cols = grid[0].size();
      if(row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] != 1)
          return;

      // 前序遍历位置，进入位置 (row, col)
      grid[row][col] = 0;                        // 将当前位置置 0
      path = path + direction + ',';            // 在路径中记录进入当前位置的方向

      // DFS 搜索上、下、左、右
      dfs(grid, row - 1, col, path, 'u');
      dfs(grid, row + 1, col, path, 'd');
      dfs(grid, row, col - 1, path, 'l');
      dfs(grid, row, col + 1, path, 'r');

      // 后序遍历位置，离开位置 (row, col)
      path = path + '-' + direction + ',';    // 在路径中记录离开当前位置的方向
  }
public:
  /**
   * @param grid: a list of lists of integers
   * @return: return an integer, denote the number of distinct islands
   */
  int numberofDistinctIslands(vector<vector<int>> &grid) {
      if(grid.size() == 0 || grid[0].size() == 0)
          return 0;

      unordered_set<string> pathMap;            // 哈希表，记录不同形状岛屿的序列化结果
      int rows = grid.size();
      int cols = grid[0].size();
      for(int row = 0; row < rows; ++row)
      {
          for(int col = 0; col < cols; ++col)
          {
              if(grid[row][col] == 1)            // 淹掉这个岛屿，并序列化
              {
                  string path;
                  dfs(grid, row, col, path, 'r');
                  pathMap.insert(path);
              }
          }
      }
      return pathMap.size();                    // 哈希表的大小，就是不同形状岛屿的数量
  }
};

复杂度分析：设矩阵 M 行 N 列

时间复杂度 O(MN)
空间复杂度 O(MN)：在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN，即空间复杂度达到 O(MN)

执行结果：

执行结果：通过

执行用时：81 ms, 在所有 C++ 提交中击败了 10.00% 的用户
内存消耗：2.18 MB, 在所有 C++ 提交中击败了 10.00% 的用户

hot 100

[中等] 694. 不同岛屿的数量

题目

解答 & 代码