代码随想录算法训练营第60期第五十五天打卡

        大家好，我们今天继续我们图论的部分，其实我们昨天是主要讲解了深搜与广搜的理论基础，我们大体上了解了两种算法的差异与适用情景，今天我们就继续我们的图论的章节，以后几天的题目是图论中比较有名的问题叫做岛屿问题，我们就开始今天的题目。

第一题对应卡码网编号为99的题目岛屿数量

       这是我们岛屿问题里面的第一题，我们是需要求岛屿的数量，我们还是先来看一下这道题目的题目要求：

        大家看我们题目给出的地图就可以了解什么样的陆地才可以叫做岛屿，首先要是水平方向或者垂直方向上相邻，但注意斜方向的不算，就比如说我们题目给出的地图很明显左上方的可以是一个岛屿，右下方的也可以是岛屿，当然中间由于跟两个岛屿是斜着连接的所以只能单独算作一个岛屿，因此我们这道题也是很适合使用深搜来解决，我们就搜索四个方向，当然要保证当前的节点没有被访问过，一个节点肯定只能属于一个岛屿，总不能一个节点既属于一个岛屿又属于另一个岛屿，还有一点大家需要注意我们搜索的过程中千万不可以超出地图的边界，因此我们可以尝试写出深搜的代码：

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};//方向数组表示上下左右四个方向
void dfs(const vector<vector<int>>&grid,vector<vector<bool>>&visited,int x,int y)
{for (int i = 0; i < 4; ++i){//这个其实是关键我们这样就可以表示所有的方向int nextx = x + dir[i][0]; int nexty = y + dir[i][1];//越界的情况要排除掉if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;//如果当前节点没有被访问过的话并且是陆地我们就可以继续搜索if (!visited[nextx][nexty] && grid[nextx][nexty]){visited[nextx][nexty] = true;dfs(grid, visited, nextx, nexty);}}return;
}
int main()
{int n, m; cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(m + 1, 0));vector<vector<bool>> visited(n + 1, vector<bool>(m + 1, 0));for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j) cin >> grid[i][j];}int count = 0;for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j) {if (!visited[i][j] && grid[i][j]){visited[i][j] = true;count++;dfs(grid, visited, i, j);}}}cout << count << '\n';return 0;
}

        当然上面是深搜的写法，那这道题目可以使用广搜的写法吗？是可以的，我们依旧可以通过广搜的写法来解决这道题目，只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。这个要注意我们广搜非常重要的点，我们广搜是借助队列来搜索的，我们只要加入队列就立马标记，这就表示我们已经访问过了这个陆地，那这样的话根据我们广搜的模板与对题目的理解我们就可以尝试给出广搜的代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
void bfs(const vector<vector<int>>&grid,vector<vector<bool>>&visited,int x,int y)
{//定义队列queue<pair<int, int>> que;//将起点添加到队列里面que.push({x, y});visited[x][y] = true; //只要加入队列立刻标记while(!que.empty()){pair<int, int> cur = que.front(); que.pop();int curx = cur.first;int cury = cur.second;for (int i = 0; i < 4; ++i){int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty>=grid[0].size()) continue; //超出边界的部分去掉if (!visited[nextx][nexty] && grid[nextx][nexty]){que.push({nextx,nexty});visited[nextx][nexty] = true;}}}
}int main()
{int n,m; cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(m + 1, 0));vector<vector<bool>> visited(n + 1, vector<bool>(m + 1, false));for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j) cin >> grid[i][j];}//存储岛屿的数量int result = 0;for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j){if (!visited[i][j] && grid[i][j]){result++;bfs(grid, visited, i, j);}}}cout << result << '\n';return 0;
}

       这个是广搜的代码，其实跟我们上次的广搜模板是一样的，以后的题目我主要只给深搜的代码，我尽力也给广搜的代码，我个人的话还是深搜用的多一些，请大家见谅！

第二题对应卡码网编号为100的题目岛屿的最大面积

        这是我们今天的第二题，我们这道题目其实跟上一道题的思路是很相似的，不过是上一道题目要求我们去找岛屿的数量而这道题则是求最大岛屿的面积，其实这道题我还是使用深搜来解决，我们其实就是不断更新岛屿面积不就可以了，其实不算难，前提是大家掌握清楚上一道题目的思路，我们还是使用深度优先搜索来给大家解决这道题目：

#include <iostream>
#include <vector>using namespace std;
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int count;
void dfs(const vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y)
{for (int i = 0; i < 4; ++i){int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;if (!visited[nextx][nexty] && grid[nextx][nexty]){count++;visited[nextx][nexty] = true;dfs(grid, visited, nextx, nexty);}}
}int main()
{int n, m; cin >> n >> m;vector<vector<int>> grid(n + 1,vector<int>(m + 1, 0));vector<vector<bool>> visited(n + 1,vector<bool>(m + 1, false));for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j) cin >> grid[i][j];}int result = 0;for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j){if (!visited[i][j] && grid[i][j]){count = 1;//最小的岛屿面积其实就是1也就是孤岛visited[i][j] = true;dfs(grid, visited, i, j);//大家注意我们这里的dfs其实不仅仅找到了岛屿而且还把岛屿面积计算出来了result = max(result, count);//不断更新岛屿的面绩}}}cout << result << '\n';return 0;
}

         当然本题的一些细节我们不可忽略，比如我们搜索的位置不能超出地图的边界，我们还要注意使用一个变量来存储所在的岛屿的面积，大家想明白这一些估计本题目就很简单了。那其实本题目使用广搜也是可以的，我们就需要使用一个队列，我可以给出广搜的代码：

class Solution {
private:int count;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<int> que;que.push(x);que.push(y);visited[x][y] = true; // 加入队列就意味节点是陆地可到达的点count++;while(!que.empty()) {int xx = que.front();que.pop();int yy = que.front();que.pop();for (int i = 0 ;i < 4; i++) {int nextx = xx + dir[i][0];int nexty = yy + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 节点没有被访问过且是陆地visited[nextx][nexty] = true;count++;que.push(nextx);que.push(nexty);}}}}public:int maxAreaOfIsland(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {count = 0;bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 trueresult = max(result, count);}}}return result;}
};

        其实这道题目比较简单，我们的深搜与广搜都可以实现，大家注意理解就可以，我们这道题就分享到这里。

今日总结

        今天我们开始接触了一些岛屿问题，其实我们发现大多都不算难，我们前提是需要掌握好深度优先搜索与广度优先搜索，理解好题意就不难了，比如说今天的这道岛屿的最大面积的题目其实只要理解好前面岛屿的数量的问题就很简单了，我们今天的分享就到这里，我们下一次博客再见！