\101. 孤岛的总面积
题目描述
给定一个由 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
输出示例
1
提示信息
在矩阵中心部分的岛屿，因为没有任何一个单元格接触到矩阵边缘，所以该岛屿属于孤岛，总面积为 1。
数据范围：
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 x,int y,vector<vector<int>>& grid)
{ //本题的grid发挥了visited的作用，所以只需要找周围的陆地即可（访问过的就变成了海洋了）//如果是海水，直接返回，不做处理if(grid[x][y]==0){return;}//边界及其相连陆地的陆地变成海洋grid[x][y]=0;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(nextx,nexty,grid);}
}
int main(void)
{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];}}//遍历边界，将边界上的陆地以及与其相连的陆地全部变成海洋，剩余grid中的陆地就是孤岛的总面积for(int i=0;i<n;i++){if(grid[i][0]==1) dfs(i,0,grid);if(grid[i][m-1]==1) dfs(i,m-1,grid);}for(int j=0;j<m;j++){if(grid[0][j]==1) dfs(0,j,grid);if(grid[n-1][j]==1) dfs(n-1,j,grid);}int result = 0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1){result++;}}}cout << result;return 0;
}