[ABC351D] Grid and Magnet

· · 题解

题解[ABC351D] Grid and Magnet

前言

这道题很难，但是我经过老师的教导，突然明悟过来，故写下此篇题解。题目传送门

思路

这道题一眼就是dfs，可是在清空数组的时候，就会快乐的TLE,TLE记录

所以让我们再次好好的想一想，到底该怎么样呢？

我们突然想到了一个方法其实不是我想到的。我们可以每次用另一个数标记，然后就不用清空了。

你明白了吗？？

AC\ 代码

//idea by wfyzlengxuenong
#include <bits/stdc++.h>
#define re register
#define il inline
#define int long long
#define endl '\n'
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

const int P = 998244353;
const int INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 1e3 + 5;

il int read() {
    re int x = 0, f = 1; re char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x * f;
}

int n, m;
int bj = 0;
int ans = 0;
int cnt = 0;
int b[maxn][maxn];
char a[maxn][maxn];
int xx[] = {0, 0, -1, 1};
int yy[] = {1, -1, 0, 0};

void dfs(int x, int y) {
    cnt ++;
    if (a[x][y] == '*') {
        return ;
    }
    for (int i = 0; i < 4; ++ i ) {
        int dx = x + xx[i];
        int dy = y + yy[i];
        if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && ((a[dx][dy] == '.' && !b[dx][dy]) || (a[dx][dy]=='*'&&b[dx][dy] != bj))){
            b[dx][dy] = bj;
            dfs(dx, dy);
        }
    }
}

signed main() {
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    //fst;

    cin >> n >> m;
    for (int i = 1; i <= n; ++ i ) {
        for (int j = 1; j <= m; ++ j ) {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i <= n; ++ i ) {
        for (int j = 1; j <= m; ++ j ) {
            if (a[i][j] == '#') {
                for (int k = 0; k < 4; ++ k ) {
                    int dx = i + xx[k];
                    int dy = j + yy[k];
                    if (a[dx][dy] != '#') {
                        a[dx][dy] = '*';
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; ++ i ) {
        for (int j = 1; j <= m; ++ j ) {
            if (a[i][j] != '#') {
                bj ++;
                cnt = 0;
                b[i][j] = bj;
                dfs(i, j);
                ans = max(ans, cnt);
            }
        }
    }
    cout << ans;

    return 0;
}