BOJ #3197 - 백조의 호수

#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define fup(i, a, b, c) for (int(i) = (a); (i) <= (b); (i) += (c))
#define fdn(i, a, b, c) for (int(i) = (a); (i) >= (b); (i) -= (c))
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int N, R, C, X;
char tmp;
int arr[1600][1600];
int p[1600 * 1600];

int find(int n) {
    if (p[n] < 0) {
        return n;
    }
    return p[n] = find(p[n]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return;
    p[a] += p[b];
    p[b] = a;
}

queue<pair<pi, int>> q;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    fill(p, p + 1600 * 1600, -1);

    cin >> R >> C;
    vector<pi> v;

    fup(i, 0, R + 1, 1) {
        fup(j, 0, C + 1, 1) {
            arr[i][j] = -1;
        }
    }

    fup(i, 1, R, 1) {
        fup(j, 1, C, 1) {
            cin >> tmp;
            if (tmp == 'L')
                v.emplace_back(i, j);
            if (tmp == 'X') {
                arr[i][j] = 1;
            } else {
                arr[i][j] = 0;
                if (i - 1 > 0 && arr[i - 1][j] == 0) {
                    merge(i * C + j, (i - 1) * C + j);
                }
                if (j - 1 > 0 && arr[i][j - 1] == 0) {
                    merge(i * C + j, i * C + j - 1);
                }
            }
        }
    }

    int flag = 0;
    if (find(v[0].first * C + v[0].second) == find((v[1].first) * C + v[1].second)) {
        flag = 1;
    }

    if (flag) {
        cout << 0;
        return 0;
    }

    fup(i, 1, R, 1) {
        fup(j, 1, C, 1) {
            if (arr[i][j] == 1) {
                fup(k, 0, 3, 1) {
                    int qx = i + dx[k], qy = j + dy[k];

                    if (arr[qx][qy] == 0) {
                        q.push({{i, j}, 0});
                        break;
                    }
                }
            }
        }
    }

    while (!q.empty()) {
        pair<pi, int> curr = q.front();
        int x = curr.first.first;
        int y = curr.first.second;
        int g = curr.second;
        q.pop();

        fup(k, 0, 3, 1) {
            int qx = x + dx[k], qy = y + dy[k];
            if (arr[qx][qy] == 0) {
                merge(qx * C + qy, x * C + y);
            } else if (arr[qx][qy] == 1) {
                int cnt = 1;
                fup(p, 0, 3, 1) {
                    int px = qx + dx[p], py = qy + dy[p];
                    if (arr[px][py] == 0) {
                        cnt = 0;
                        break;
                    }
                }
                if (cnt)
                    q.push({{qx, qy}, g + 1});
            }
        }

        arr[x][y] = 0;

        int flag = 0;
        if (find(v[0].first * C + v[0].second) == find((v[1].first) * C + v[1].second)) {
            flag = 1;
        }

        if (flag) {
            cout << g + 1;
            return 0;
        }
    }
}