D. Lakes in Berland

 1 #include<iostream> 2 #include<queue> 3 #include<vector> 4 #include<functional> 5 using namespace std; 6  7 typedef pair<int, int> P; 8 typedef pair<int, P> PP; 9 const int maxn = 55;10 char map[maxn][maxn];11 int vis[maxn][maxn];12 int dx[4] = { 1,0,-1,0 };13 int dy[4] = { 0,1,0,-1 };14 int n, m, sum, fg;15 priority_queue<PP, vector<PP>, greater<PP> > lake;16 17 void dfs(P s)18 {19     int x = s.first, y = s.second;20     sum++;21     vis[x][y] = 1;22     if (x == 1 || x == n || y == 1 || y == m) fg = 0;23     for (int i = 0; i < 4; i++)24     {25         int nx = x + dx[i];26         int ny = y + dy[i];27         if (nx < 1 || nx > n) continue;28         if (ny < 1 || ny > m) continue;29         if (map[nx][ny] == ‘*‘) continue;30         if (vis[nx][ny]) continue;31         dfs(P(nx, ny));32     }33 }34 35 void dfs2(P s)36 {37     int x = s.first, y = s.second;38     map[x][y] = ‘*‘;39     for (int i = 0; i < 4; i++)40     {41         int nx = x + dx[i];42         int ny = y + dy[i];43         if (nx < 1 || nx > n)continue;44         if (ny < 1 || ny > m)continue;45         if (map[nx][ny] == ‘*‘)continue;46         dfs2(P(nx, ny));47     }48 }49 50 int main()51 {52     int k;53     cin >> n >> m >> k;54     for (int i = 1; i <= n; i++)55         for (int j = 1; j <= m; j++)56             cin >> map[i][j];57     for (int i = 1; i <= n; i++)58         for (int j = 1; j <= m; j++)59             if (map[i][j] == ‘.‘ && vis[i][j] == 0) {60                 fg = 1;61                 sum = 0;62                 dfs(P(i, j));63                 if (fg) lake.push(PP(sum, P(i, j)));64             }65     int ans = 0;66     while (lake.size() != k) {67         ans += lake.top().first;68         dfs2(lake.top().second);69         lake.pop();70     }71     cout << ans << endl;72     for (int i = 1; i <= n; i++) {73         for (int j = 1; j <= m; j++)74             cout << map[i][j];75         cout << endl;76     }77     return 0;78 }