\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。
数据范围：
1 <= M, N <= 50。
#include<iostream>
#include<vector>
using namespace std;
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
void dfs(int& cnt,vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y)
{//这种dfs的写法处理的是当前节点if(grid[x][y]==0 || visited[x][y]){return;}cnt++; //一定是一块没有被访问过的陆地visited[x][y]=true;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;dfs(cnt,grid,visited,nextx,nexty);}
}
int main(void)
{int n,m;cin >> n >> m;vector<vector<int>> grid(n,vector<int>(m,0));vector<vector<bool>> visited(n,vector<bool>(m,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(grid[i][j]==1 && !visited[i][j]){int cnt = 0;dfs(cnt,grid,visited,i,j);result = max(cnt,result);}}}cout << result << endl;return 0;
}
- 和前面的题目区别不大，就是统计每一块岛屿的面积，找出最大值