Hướng dẫn giải của Cuộc hội ngộ của 2 chú ếch

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Sử dụng DSU để hợp các ô là ô nước ở cạnh nhau. 2 chú ếch chỉ đến được với nhau khi và chỉ khi chúng cùng một tập hợp. Với mỗi ngày qua đi, xét từng ô băng tan ra (tính ngày tan ra của băng sử dụng BFS đa luồng), join các ô nước xung quanh lại và kiểm tra xem 2 chú ếch đã ở cùng tập hợp chưa.

Code

#include <bits/stdc++.h>
using namespace std;

#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end());
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"

const int maxn = 1505;
const int dir[4][2] = {
    {1, 0},
    {0, 1},
    {-1, 0},
    {0, -1},
};

int ds[maxn][maxn];
char c[maxn][maxn];
vector<int> l;
vector<pi> ice[maxn * 2 + 69];
queue<pi> q;
int n, m;


struct DisjointSet{
    vector<int> parent;
    DisjointSet(int n): parent(n + 1){
        for(int i = 1; i <= n; i++) parent[i] = i;
    }

    int find(int u){
        if(u != parent[u]) return parent[u] = find(parent[u]);
        return u;
    }

    bool join(int u, int v){
        u = find(u);
        v = find(v);
        if(u == v) return false;
        parent[u] = v;
        return true;
    }
};

inline bool valid(int x, int y){
    return x && y && x <= n && y <= m;
}

inline int id(int x, int y){
    return (x - 1) * m + y;
}

void bfs(){
    while(q.size()){
        int x = q.front().first,
            y = q.front().second;
        q.pop();
        if(c[x][y] == 'X') ice[ds[x][y]].push_back({x, y});
        for(int i = 0; i < 4; i++){
            int a = x + dir[i][0],
                b = y + dir[i][1];
            if(!valid(a, b)) continue;
            if(ds[a][b] == inf64) ds[a][b] = ds[x][y] + 1, q.push({a, b});
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    DisjointSet d(n * m + 12);
    setinf(ds);
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){
        cin >> c[i][j];
        if(c[i][j] == 'L') l.push_back(id(i, j));
        if(c[i][j] != 'X'){
            for(int k = 0; k < 4; k++){
                int a = i + dir[k][0],
                    b = j + dir[k][1];
                if(valid(a, b) && c[a][b] != 'X') d.join(id(i, j), id(a, b));
            }
            q.push({i, j}), ds[i][j] = 0;
        }
    }

    bfs();
    int ans = 0;
    do{
        if(d.find(l.front()) == d.find(l.back())) return cout << ans, 0;
        ans++;
        for(pi &p : ice[ans]){
            c[p.first][p.second] = '.';
            for(int i = 0; i < 4; i++){
                int x = p.first + dir[i][0],
                    y = p.second + dir[i][1];
                if(!valid(x, y)) continue;
                if(c[x][y] != 'X' || ds[x][y] == ans) d.join(id(p.first, p.second), id(x, y));
            }
        }
    }while(1);


}