圖--

題目描述

研究地球空間科學的永強想研究海岸線的長度和海岸線面積之間的關系，為此他找來了很多航拍圖像。在航拍圖像上利用圖像分割的方法，把圖像的每個像素标記成陸地（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;
}