DAY56 ||99.岛屿数量 深搜 |99.岛屿数量 广搜 |100.岛屿的最大面积
99.岛屿数量 深搜
99. 岛屿数量
给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。
后续 N 行，每行包含 M 个数字，数字为 1 或者 0。
输出描述
输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。
输入示例
4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1输出示例
3
思路
首先自定义四个遍历方向，以纵向为x轴，横向为y轴。于是可以定义出
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向{0，1}代表向右，{1，0}代表向下移动，{-1，0}代表向上，{0，-1}代表向左。（注意向下为正方向）
首先初始化访问情况皆为false。然后grid数组记录陆地和海洋的情况。
先两层循环遍历岛屿，遇到未访问过的陆地就result+1(main主函数)，然后深度搜索（dfs函数）是否有邻近陆地，记为true（访问过）。
乍一看复杂，其实不难。据说这是模板提？？
代码
#include<iostream>
#include<vector>
using namespace std;
//深度搜索
int dir[4][2]={0, 1, 1, 0, -1, 0, 0, -1}; // 右，上，下，左
void dfs(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]==1)//如果没访问过且是陆地则是相邻的
{
visited[nextx][nexty]=true;
dfs(grid,visited,nextx,nexty);//深度搜索
}
}
}
int main()
{
int n,m;
cin>>n>>m;//输入网格的行数和列数
vector<vector<int>>grid(n,vector<int>(m,0));
//输入陆地和水域的状况
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>grid[i][j];
}
}
vector<vector<bool>>visited(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)//如果该陆地未被访问过
{
visited[i][j]=true;
result++;//岛屿数量加一
dfs(grid,visited,i,j);//继续深度搜索岛屿，把相邻的陆地标记为访问过
}
}
}
cout<<result<<endl;
}下一个节点是否能合法已经判断完了，传进dfs函数的就是合法节点。
99.岛屿数量 广搜
思路
顾名思义四个方向一起探索？？
根本原因是只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。
注意和深搜区别是，这里一旦一个坐标传进去入列标记，就要while循环查探完四个方向的情况提取队列的首坐标，然后只要需要未访问的且是陆地的，立马入列标记，没有递归。
函数流程：
queue<pair<int, int>> que;：声明一个队列que，队列中的元素是pair<int, int>类型，用于存储坐标。
que.push({x, y});：将起始位置(x, y)入队。
visited[x][y] = true;：将起始位置标记为已访问。
while(!que.empty())：当队列不为空时，循环继续执行。
pair<int, int> cur = que.front(); que.pop();：取出队列中的第一个元素，并弹出它。
cur.first和cur.second分别是当前格子的x和y坐标。- 然后遍历四个方向，尝试访问当前格子的四个相邻位置。
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] == 1)：如果相邻位置是陆地（grid[nextx][nexty] == 1）并且没有被访问过（!visited[nextx][nexty]），则将该位置加入队列，表示需要继续访问。que.push({nextx, nexty});：将相邻位置加入队列。visited[nextx][nexty] = true;：将相邻位置标记为已访问。当队列为空时，说明与起始位置相连的所有陆地已经被访问完
代码
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
//广度搜索
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<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] == 1) {
que.push({nextx, nexty});
visited[nextx][nexty] = true; // 只要加入队列立刻标记
}
}
}
}
int main()
{
int n,m;
cin>>n>>m;
vector<vector<int>>grid(n,vector<int>(m,0));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>grid[i][j];
}
}
int result=0;
vector<vector<bool>>visited(n,vector<bool>(m,false));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!visited[i][j]&&grid[i][j]==1)//如果是未访问的陆地
{
result++;
bfs(grid,visited,i,j);//不需要标记当前遍历的坐标，标记周围的
}
}
}
cout<<result<<endl;
}
100.岛屿的最大面积
基础题
100. 岛屿的最大面积
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。
输入示例
4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1输出示例
4提示信息
样例输入中，岛屿的最大面积为 4。
和岛屿数量很像，感觉也是模板题，唯一区别是记录最多相邻岛屿数量？就是岛屿最大面积。
喜欢dfs写法，就写dfs吧。
思路就是每一遍深搜的时候记录岛屿数量，一个坐标深搜完回来和result比较，最更大谁就成为新的result值。
代码
dfs只处理下一个节点，即在主函数遇到岛屿就计数为1，dfs处理接下来的相邻陆地。
#include <iostream>
#include <vector>
using namespace std;
int count;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(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] == 1) { // 没有访问过的 同时 是陆地的
visited[nextx][nexty] = true;
count++;
dfs(grid, visited, nextx, nexty);
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
vector<vector<bool>> visited(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 = 1; // 因为dfs处理下一个节点，所以这里遇到陆地了就先计数，dfs处理接下来的相邻陆地
visited[i][j] = true;
dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
result = max(result, count);
}
}
}
cout << result << endl;
}还有写法二，dfs处理当前节点，即在主函数遇到岛屿就计数为0，dfs处理接下来的全部陆地
外加广搜。