Codeforces Round #375 (Div. 2) D. Lakes in Berland __ dfs+贪心+小根堆

Source

Codeforces Round #375 (Div. 2)

My Solution

dfs+贪心+小根堆

枚举所有未被标记过的 '.' 点， 先跑一遍dfs，如果是湖(没有到四周边界)，则再跑一边来找出这个湖的大小，并记录在小根堆里 pq.push(ii(cnt, make_pair(i, j)));

然后对于pq里最小的前 pq.size() - k 个湖，跑一遍dfs把湖填上。//初始坐标为 (pq.top().second.first, pq.top().second.second)

然后MLE了，其实应该TLE吧，嘿嘿

dfs的时候没有处理本次dfs时访问过的点，所以可能跳不出递归即超内存也超时，所以每次dfs用 一个bool v[maxn][maxn] 数组标记，且每次使用前重置。

这样每次dfs每个点最多访问一次。

每个湖只找的时候访问2次，处理的时候访问一次，故每个点最多访问3次，

故 复杂度 O(n^2)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<int, pair<int, int> > ii;
const int maxn = 50 + 8;

string s[maxn];
bool vis[maxn][maxn], v[maxn][maxn];
priority_queue<ii, vector, greater > pq;
int n, m, k, cnt;

bool flag;
void dfs(int x, int y, int orix, int oriy)
{
    if(v[x][y]) return;
    if(s[x][y] == '*') return;
    else{
        if(x == 0 || x == n - 1 || y == 0 || y == m - 1) {flag = false; return;}
    }
    v[x][y] = true;
    if(x + 1 < n && !(x + 1 == orix && y == oriy) ){ dfs(x + 1, y, x, y); } if(x - 1 >= 0 && !(x - 1 == orix && y == oriy) ){
        dfs(x - 1, y, x, y);
    }
    if(y + 1 , m && !(x == orix && y + 1 == oriy) ){
        dfs(x, y + 1, x, y);
    }
    if(y - 1 >= 0 && !(x == orix && y - 1 == oriy) ){
        dfs(x, y - 1, x, y);
    }
}

void _find(int x, int y, int orix, int oriy)
{
    if(v[x][y]) return;
    if(s[x][y] == '*') return;
    else{
        cnt++;
        vis[x][y] = true;
    }
    v[x][y] = true;
    if(x + 1 < n && !(x + 1 == orix && y == oriy) ){ _find(x + 1, y, x, y); } if(x - 1 >= 0 && !(x - 1 == orix && y == oriy) ){
        _find(x - 1, y, x, y);
    }
    if(y + 1 , m && !(x == orix && y + 1 == oriy) ){
        _find(x, y + 1, x, y);
    }
    if(y - 1 >= 0 && !(x == orix && y - 1 == oriy) ){
        _find(x, y - 1, x, y);
    }
}

void fillup(int x, int y, int orix, int oriy)
{
    if(v[x][y]) return;
    if(s[x][y] == '*') return;
    else{
        //cnt++;
        //vis[x][y] = true;
        ;
    }
    v[x][y] = true;
    if(x + 1 < n && !(x + 1 == orix && y == oriy) ){ fillup(x + 1, y, x, y); } if(x - 1 >= 0 && !(x - 1 == orix && y == oriy) ){
        fillup(x - 1, y, x, y);
    }
    if(y + 1 , m && !(x == orix && y + 1 == oriy) ){
        fillup(x, y + 1, x, y);
    }
    if(y - 1 >= 0 && !(x == orix && y - 1 == oriy) ){
        fillup(x, y - 1, x, y);
    }
    //»ØËݵÄʱºò fillup
    s[x][y] = '*';
}


int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int ans = 0;
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++){ cin >> s[i];
    }
    int i, j;
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
            if(vis[i][j]) continue;
            if(s[i][j] == '*') continue;
            flag = true;
            memset(v, false, sizeof v);
            dfs(i, j, i, j);
            if(flag){
                cnt  = 0;
                memset(v, false, sizeof v);
                _find(i, j, i, j);
                if(cnt){
                    pq.push(ii(cnt, make_pair(i, j)));
                }
            }
        }
    }
    int t = pq.size() - k;
    while(t--){
        ans += pq.top().first;
        memset(v, false, sizeof v);
        fillup(pq.top().second.first, pq.top().second.second, pq.top().second.first, pq.top().second.second);
        pq.pop();
    }

    cout << ans << endl;
    for(int i = 0; i < n; i++){
        cout << s[i] << "n";
    }


    #ifdef LOCAL
    memset(vis, false, sizeof vis);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx