问题描述

小 G 最近开始对地理感兴趣，小 G 找来了伯兰的地图，并用网格将其划分。被划分后

的地图是一个 n*m 的矩形。每一个单元格的大小是 1*1 的，每一格代表着水或者陆地。地

图外则代表着海洋。湖泊是相邻的所有代表水的格子组成的不与海洋相邻的最大区域。地图

上有着超过 k 的湖泊，小 G 想将其中的一些代表水的格子变为陆地，使得地图中只存在精

确的 k 个湖泊，又不想改变太多的格子。所以，他请你帮忙计算使得地图中只存在 k 个湖泊

所需要改变的最小格子数。

★数据输入

输入的第一行为包括三个整数n,m,k(1 ≤ n, m ≤ 50, 0 ≤ k ≤ 50)表示地图的大小和需

要保存的湖泊数量。

接下来 n 行，每行包括 m 个字符用来表示地图信息，只包括“.”和“*”两种字符。（ “.”

表示水， “*”表示陆地）。

输入数据保证原始的湖泊数量大于等于 k。

30%的数据 n*m<=30。

70%的数据 n*m<=200。

100%的数据 n*m<=2500。

题意：

给n，m和k，n和m为所给矩阵的高和宽。k是要求最多剩下的湖的数量。

在所给的矩阵中，*代表陆地，.代表水。

湖的定义是一片连续的水（上下左右四个方向），并且水不含边界。

水含边界的情况被成为海。

问最少填多少湖的面积，使得湖的数量减少到k.

海洋包围的小岛，岛内的有湖，'.'代表水，'*'代表陆地，给出的n*m的地图里至少有k个湖，求填掉面积尽量少的水，使得湖的数量正好为k。

解题思路：先深搜DFS找出所有的湖泊，然后按照面积从小到大排序，若湖的数量为cnt，填掉前cnt-k个湖。

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;//author:zeze 2016-12-11 13:24:39//DFS+Greedystruct lakes{    int x,y;//lake site    int num;//lake size}lake[2500];bool cmp(lakes a,lakes b){    return a.num
         
          =0&&xx
          
           =0&&yy
           
            =0&&xx
            
             =0&&yy
            
           
          
         
        
       
      
     

 

 

#include
     
      using namespace std;int n,m,k;char a[55][55];bool vis[55][55];int dx[6]={
   0,0,1,-1};int dy[6]={
   1,-1,0,0};int num,cnt,islake;int ans;struct lake{    int x,y;    int num;    int id;}lk[2600];bool cmp(lake a,lake b){    return a.num
      
       =0&&nx
       
        
         =0&&a[nx][ny]=='.'&&!vis[nx][ny])            dfs(nx,ny);    }}void fil(int x,int y,int id){    vis[x][y]=1;    ans++;    a[x][y]='*';//填充这个湖    for(int i=0;i<4;i++){        int nx=x+dx[i],ny=y+dy[i];        if(nx>=0&&nx
         
          
           =0&&a[nx][ny]=='.'&&!vis[nx][ny]) fil(nx,ny,id); }}int main(){ cnt=0; scanf("%d%d%d",&n,&m,&k); for(int i=0;i