题意：n*m个格子，有*和.两种类型。定义一个湖为边相邻的只有.组成的最大点集合，且任何一个.不在边界上。现在给出一个n*m的图保证至少有k个湖。问填多少个.成*，才能使得恰好有k个湖。
思路：贪心，先处理出所有的湖的大小，然后从小往大填。
注意dfs的时候如果某个“可能”的湖遇到了边界，要把之前打的标记撤销掉。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
/* *********************************************** Author :111qqz Created Time :2016年10月03日 星期一 21时18分03秒 File Name :code/cf/#375/D.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <deque> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <bitset> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0};tanxin const int inf = 0x3f3f3f3f; const int N=55; char maze[N][N]; int n,m,k; int vis[N][N]; int lake_cnt=0; int siz; struct node { int id; int val; bool operator < (node b)const { return val<b.val; } }lake[N*N]; bool die ; set< pi >se; void dfs( int x,int y) { if (die) return; siz++; // cout<<"x:"<<x<<" y: "<<y<<endl; for ( int i = 0 ; i < 4 ; i++) { int nx = x + dx4[i]; int ny = y + dy4[i]; if (maze[nx][ny]=='*') continue; if (nx==0||nx==n-1||ny==0||ny==m-1) { die = true; return; } if (vis[nx][ny]!=0) continue; vis[nx][ny] = lake_cnt; se.insert(make_pair(nx,ny)); dfs(nx,ny); } } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif cin>>n>>m>>k; for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]); ms(vis,0); for ( int i = 1 ; i < n-1 ; i++) { for ( int j = 1 ; j < m-1 ; j++) { if (maze[i][j]=='.'&&!vis[i][j]) { se.clear(); siz = 0 ; vis[i][j] = ++lake_cnt; se.insert(make_pair(i,j)); die = false; dfs(i,j); if (die) { for ( auto it = se.begin () ; it!=se.end() ;it++) { pi tmp = *it; vis[tmp.fst][tmp.sec] = 0 ; } lake_cnt--; } else { lake[lake_cnt].val=siz; lake[lake_cnt].id = lake_cnt; } } } } sort(lake+1,lake+lake_cnt+1); map<int,int>mp; for ( int i = 1 ; i <= lake_cnt ; i++) mp[lake[i].id] = i; // for ( int i = 0 ; i < n ; i++) // { // for ( int j = 0 ; j < m ; j++) // { // printf("%d ",vis[i][j]); // } // printf("\n"); // } for ( int i = 1 ; i < n-1 ; i++) { for ( int j = 1 ; j < m-1; j++) { if (maze[i][j]=='*') continue; int v = vis[i][j]; if (v==0) continue; if (mp[v]<=lake_cnt-k) maze[i][j]='*'; } } int ans = 0 ; for ( int i = 1 ; i <= lake_cnt-k ; i++) ans = ans + lake[i].val; printf("%d\n",ans); for ( int i = 0 ; i < n ; i++) printf("%s\n",maze[i]); #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人！