Codeforces Round #375 (Div. 2)

Codeforces Round #375 (Div. 2) - D

阅读量：7175 次

发布时间：2019-06-29

本文共 989 字，大约阅读时间需要 3 分钟。

题目链接：http://codeforces.com/contest/723/problem/D

题意：给定n*m小大的字符矩阵。'*'表示陆地,'.'表示水域。然后湖的定义是：如果水域完全被陆地包围则称为湖。海的定义：如果水域与任何一个边界的水域有连通则陈伟海。现在要求填一些湖使得最后湖的数量恰好等于K.输出最小要填多少个单位的'.'水域和最终填完之后的字符矩阵。

思路：水题。注意本题的连通是四个方向[上下左右]，然后dfs每一个连通块，对于每个连通块我们维护2个值:水域的数目和连通块属于海还是湖。假装最终一共有x个湖。则要填(x-k)个湖。所以对于湖我们找水域最小的哪些连通块来填。

#define _CRT_SECURE_NO_DEPRECATE#include
     
        #include
      
         #include
       
        #include
        
           #include
         
            #include
          
            #include
           
            #include
            #include
             
              #include
              
               using namespace std;typedef long long int LL;const int INF = 0x3f3f3f3f;const int MAXN = 50 + 10;int n, m, k, vis[MAXN][MAXN], id;char G[MAXN][MAXN];int dist[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };struct Node{ int cnt; //水域数目 bool flag; //true: 海 false:湖}sea[MAXN*MAXN];bool check(int x, int y){ //是否越界 return x >= 0 && x
               
                = 0 && y
                
                 k; totk--){ int minval = INF, minid = 0; for (int i = 1; i

转载于:https://www.cnblogs.com/kirito520/p/5930089.html

你可能感兴趣的文章