图--

题目描述

研究地球空间科学的永强想研究海岸线的长度和海岸线面积之间的关系，为此他找来了很多航拍图像。在航拍图像上利用图像分割的方法，把图像的每个像素标记成陆地（1）和水面（0）。

示例图片：

 

现在永强想知道每张图中陆地部分的面积。

 

已知每张图最底部的一条边都是陆地，并且在一张图上陆地都是四邻域联通的。

但是永强发现分割的结果有很多的噪声，于是他定义了如下规则试图去除噪声：

a)    如果一个水面区域被陆地包围，则将这个区域记为陆地；
b)    在a的基础上如果一个陆地区域不和底边的陆地相连，那么这是一个岛屿，不计入陆地的面积。

 

输入描述:

第一行为两个整数m和n，
接下来m行每行会有n个数，0表示水面，1表示陆地。

输出描述:

去噪后陆地部分的面积。

示例1

输入

复制

5 6
1 0 0 1 0 0
0 0 1 0 1 0
1 1 1 1 1 0
1 0 0 1 1 1
1 1 1 1 1 1

输出

复制

21

#include<vector>
#include<iostream>
using namespace std;

int m,n;

void Link(const int Key,int x,int y,const int Set,vector<vector<int>>& Map,int& sum)
{
if(Map[x][y] == Key){
sum++;
Map[x][y] = Set;
if(x - 1 >= 0 && Map[x - 1][y] == Key){
Link(Key,x - 1,y,Set,Map,sum);
        }
if(x + 1 < m && Map[x + 1][y] == Key){
Link(Key,x + 1,y,Set,Map,sum);
        }
if(y - 1 >= 0 && Map[x][y - 1] == Key){
Link(Key,x,y - 1,Set,Map,sum);
        }
if(y + 1 < n && Map[x][y + 1] == Key){
Link(Key,x,y + 1,Set,Map,sum);
        }
    }
else{
return;
    }
}

int main(){
int sum = 0;
cin >> m >> n;
vector<vector<int>> Map(m,vector<int>(n,0));
for(int i = 0;i < m;i ++){
for(int j = 0;j < n;j ++){
int tmp;
scanf("%d",&tmp);
Map[i][j] = tmp;
        }
    }
for(int i = 0;i < n;i ++){
if(Map[0][i] == 0){
Link(0,0,i,-1,Map,sum);
        }
    }
for(int i = 0;i < m;i ++){
if(Map[i][0] == 0){
Link(0,i,0,-1,Map,sum);
        }
if(Map[i][n - 1] == 0){
Link(0,i,n - 1,-1,Map,sum);
        }
    }
for(int i = 0;i < m;i ++){
for(int j = 0;j < n;j ++){
if(Map[i][j] == 0){
Map[i][j] = 1;
            }
        }
    }
sum = 0;
Link(1,m - 1,0,2,Map,sum);
printf("%d\n",sum);
return 0;
}