2.岛屿数量
题目描述：
给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述：
第一行包含两个整数 N, M，表示矩阵的行数和列数。
后续 N 行，每行包含 M 个数字，数字为 1 或者 0。
输出描述：
输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。
深搜思路：利用深度搜索，每一执行dfs就将几块连在一起的陆地全部标记为已访问，result++记录一个岛屿，然后再继续遇到下一个未被访问过的陆地时执行dfs，然后result++……
方向控制
int dir[4][2] = {{0, 1}, // 向右{1, 0}, // 向下{-1, 0}, // 向上{0, -1} // 向左
};dir[i][j] 的具体值
i | j | dir[i][j] 值 | 意义 |
|---|---|---|---|
0 | 0 | 0 | 行不变 |
0 | 1 | 1 | 列增加 1（向右） |
1 | 0 | 1 | 行增加 1（向下） |
1 | 1 | 0 | 列不变 |
2 | 0 | -1 | 行减少 1（向上） |
2 | 1 | 0 | 列不变 |
3 | 0 | 0 | 行不变 |
3 | 1 | -1 | 列减少 1（向左） |
代码：
#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {{0, 1}, // 向右{1, 0}, // 向下{-1, 0}, // 向上{0, -1} // 向左
};
//四个方向：右，下，上，左
//dir[x][y],x代表行，y代表列，列加1是右移，减一是左移，行加1是下移，行减一是上移
void dfs(const vector<vector<int>>&grid,vector<vector<bool>>&visited,int x,int y )
{//终止条件if(visited[x][y]==true || grid[x][y]==0)//访问过或者是海水就终止{return;}visited[x][y]=true;//将传入的位置设为已访问//循环开始，向四个方向移动for(int i=0;i<4;i++)//{int nextx = x + dir[i][0];//y不变，二维数组dir中每一维的第一个元素都是xint nexty = y + dir[i][1];if(nextx<0 || nextx>=grid.size()|| nexty<0 || nexty>=grid[0].size()){continue;//越界}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];}}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]==false && grid[i][j]==1){result++;//遇到没访问过的陆地dfs(grid,visited,i,j);}}}cout<<result<<endl;return 0;}3.岛屿的最大面积
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。
//思路把上一题的代码增加一个面积计数器即可
#include <iostream>
#include <vector>
using namespace std;
int dir[4][2]={0,1,0,-1,-1,0,1,0};
int count=0;
vector<int>result;
void dfs(const vector<vector<int>>&grid,vector<vector<bool>>&visited,int x,int y)
{if(visited[x][y]==true || grid[x][y]==0)//终止条件{return;}visited[x][y]=true;count++;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]==false && grid[nextx][nexty]==1){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));for(int i=0;i<n;i++){for(int j=0;j<m;j++){dfs(grid,visited,i,j);result.push_back(count);//记录面积的数组count=0;//重置计数器}}int max=0;for(int i=0;i<result.size();i++){if(result[i]>max){max = result[i];}}cout<<max<<endl;return 0;
} 还有一种写法：
for(int i=0;i<n;i++){for(int j=0;j<m;j++){dfs(grid,visited,i,j);result = max(result,count);count=0;}}cout<<result<<endl;更节省空间
1.岛屿数量
广搜思路：本题思路:遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。
再遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。
重点：只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过
//后者为什么不行可以看下方gpt老师的解释
代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2]={0,1,1,0,-1,0,0,-1};
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]==false && grid[nextx][nexty]==1){//未被访问过的陆地que.push({nextx,nexty});visited[nextx][nexty]=true;//只要加入队列就立马标记}}}return;
}
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]==false && grid[i][j]==1){result++;bfs(grid,visited,i,j);}}}cout<<result<<endl;return 0;}
