前言
中等 √ 做得我元气大伤，超级naive方法，新开辟一个数组存岛屿编号，一个数组存岛屿上的点。
题目
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"] ] 输出：1
示例 2：
输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"] ] 输出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
思路
用一个二维数组存每个岛对应的点，一个二维数组存每个点对应的岛（岛屿编号）。遍历每个点，如果为1则进行判断，左上都没岛屿，新开辟一个岛；左边和上边任意一边有岛屿或者为相同岛屿，加入该岛；左边和上边都有岛屿且不是同一个岛，合并两岛并加入该岛，具体做法为把一个岛的点全部接到另一个岛上，更新island和index，注意此时原本的island的点为空。最后遍历island，不为空的岛的数量即为解集。
我的题解
class Solution {
public:int numIslands(vector<vector<char>>& grid) {if (grid.empty()) return 0; int m = grid.size();int n = grid[0].size();vector<vector<pair<int, int>>> island;vector<vector<int>> index(m, vector<int>(n, -1));int count = 0;for (int i = 0; i < grid.size(); i++){for (int j = 0; j < grid[0].size(); j++){int left = -1, top = -1;if (grid[i][j] == '1'){if (i > 0)top = index[i-1][j];if (j > 0)left = index[i][j-1];//左上都没岛屿，新建一岛//左上一边有岛屿或左上岛屿相同，加入该岛//左上岛屿不同，合并两岛if (left == -1 && top == -1){//更新inland，indexisland.push_back({{i, j}});index[i][j] = count;count++;}else{if (top == -1 || left == -1 || top == left){int temp = max(left, top);island[temp].push_back({i,j});index[i][j] = temp;}else{//合并两岛, left移到上边int temp1 = min(top, left);int temp2 = max(top, left);island[temp1].push_back({i,j});index[i][j] = temp1;for (int i = 0; i < island[temp2].size(); i++){pair<int, int> temp = island[temp2][i];index[temp.first][temp.second] = temp1; }island[temp1].insert(island[temp1].end(), island[temp2].begin(), island[temp2].end());island[temp2] = {}; }}}}}int ans = 0;for (int i = 0; i < island.size(); i++){if (!island[i].empty())ans++;}return ans;}
};官方题解
深度优先搜索
我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
最终岛屿的数量就是我们进行深度优先搜索的次数。
class Solution {
private:void dfs(vector<vector<char>>& grid, int r, int c) {int nr = grid.size();int nc = grid[0].size();grid[r][c] = '0';if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);}public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if (!nr) return 0;int nc = grid[0].size();int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {++num_islands;dfs(grid, r, c);}}}return num_islands;}
};广度优先搜索
同样地，我们也可以使用广度优先搜索代替深度优先搜索。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。
最终岛屿的数量就是我们进行广度优先搜索的次数。
class Solution {
public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if (!nr) return 0;int nc = grid[0].size();int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {++num_islands;grid[r][c] = '0';queue<pair<int, int>> neighbors;neighbors.push({r, c});while (!neighbors.empty()) {auto rc = neighbors.front();neighbors.pop();int row = rc.first, col = rc.second;if (row - 1 >= 0 && grid[row-1][col] == '1') {neighbors.push({row-1, col});grid[row-1][col] = '0';}if (row + 1 < nr && grid[row+1][col] == '1') {neighbors.push({row+1, col});grid[row+1][col] = '0';}if (col - 1 >= 0 && grid[row][col-1] == '1') {neighbors.push({row, col-1});grid[row][col-1] = '0';}if (col + 1 < nc && grid[row][col+1] == '1') {neighbors.push({row, col+1});grid[row][col+1] = '0';}}}}}return num_islands;}
};并查集
同样地，我们也可以使用并查集代替搜索。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并。
最终岛屿的数量就是并查集中连通分量的数目。
class UnionFind {
public:UnionFind(vector<vector<char>>& grid) {count = 0;int m = grid.size();int n = grid[0].size();for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == '1') {parent.push_back(i * n + j);++count;}else {parent.push_back(-1);}rank.push_back(0);}}}int find(int i) {if (parent[i] != i) {parent[i] = find(parent[i]);}return parent[i];}void unite(int x, int y) {int rootx = find(x);int rooty = find(y);if (rootx != rooty) {if (rank[rootx] < rank[rooty]) {swap(rootx, rooty);}parent[rooty] = rootx;if (rank[rootx] == rank[rooty]) rank[rootx] += 1;--count;}}int getCount() const {return count;}private:vector<int> parent;vector<int> rank;int count;
};class Solution {
public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if (!nr) return 0;int nc = grid[0].size();UnionFind uf(grid);int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {grid[r][c] = '0';if (r - 1 >= 0 && grid[r-1][c] == '1') uf.unite(r * nc + c, (r-1) * nc + c);if (r + 1 < nr && grid[r+1][c] == '1') uf.unite(r * nc + c, (r+1) * nc + c);if (c - 1 >= 0 && grid[r][c-1] == '1') uf.unite(r * nc + c, r * nc + c - 1);if (c + 1 < nc && grid[r][c+1] == '1') uf.unite(r * nc + c, r * nc + c + 1);}}}return uf.getCount();}
};知识点
开辟静态数组：vector<vector<int>> index(m, vector<int>(n, -1));
数组置空：island[temp2] = {};
心得
这个题目做了好久....重新做图的题已经忘了一般怎么解了，只会当成一个普通数组，在好多个测试案例报错之后不断debug，终于完成了我的“笨”方法，感觉有点类似并集法且不会改变图原有的结构和内容，不过题解的并集法太复杂了，故只学习一下dfs和bfs。核心是顺着陆地向上下左右四个方向搜陆地，搜到的陆地标为0，这样在重新进行搜索的时候就是一块“新大陆”，即题解。虽然这个题目没想到标准解法，但我的解法也是可行而且时空复杂度相同，并且实现了额外的功能：点->岛，岛->点。所以不要气馁，积累积累，思考才是最可贵的！！噢，另外数组/容器的用法学习要系统化一下了，这么基础的用法不能老是问ai~
