#include "labirintus.h"
#include <algorithm>

using namespace std;

int M, R, C;
vector<vector<int>> labyrinth;
vector<int> sz, par;
vector<pair<int,int>> hist;

int find_par(int x) {
    return x==par[x] ? x : find_par(par[x]);
}

void unite(int r1, int c1, int r2, int c2, bool save=false) {
    int x = r1*C+c1, y;
    if (r2<0 || r2>=R) y = (r2==R ? M-2 : M-1);
    else if (c2<0 || c2>=C) y = (c2==C ? M-1 : M-2);
    else y = r2*C+c2;

    x = find_par(x), y = find_par(y);
    if (x==y) return;
    if (sz[x] < sz[y]) swap(x,y);
    sz[x] += sz[y];
    par[y] = x;
    if (save) hist.push_back({x, y});
}

void init_labyrinth(int _R, int _C, std::vector<std::vector<int>> L) {
    R = _R, C = _C;
    labyrinth = L;
    M = R*C+2;
    sz.assign(M, 1), par.resize(M);
    for (int i=0; i<M; ++i) par[i] = i;
    for (int i=0; i<R; ++i) {
        for (int j=0; j<C; ++j) {
            if (labyrinth[i][j] == 0) continue;
            for (int x=i-1; x<=i+1; ++x)
                for (int y=j-1; y<=j+1; ++y)
                    if (x<0 || x>=R || y<0 || y>=C || labyrinth[x][y] == 1)
                        unite(i,j, x,y);
        }
    }
}

bool can_escape(int N, std::vector<int> U, std::vector<int> V) {
    hist.clear();
    for (int k=0; k<N; ++k) {
        int i = U[k], j = V[k];
        for (int x=i-1; x<=i+1; ++x)
            for (int y=j-1; y<=j+1; ++y)
                if (x<0 || x>=R || y<0 || y>=C || labyrinth[x][y] == 1) 
                    unite(i,j, x,y, true);
        labyrinth[i][j] = 1;
    }
    bool ans = (find_par(M-2) != find_par(M-1));
    reverse(hist.begin(), hist.end());
    for (auto [x,y] : hist) {
        par[y] = y;
        sz[x] -= sz[y];
    }
    for (int k=0; k<N; ++k) {
        labyrinth[U[k]][V[k]] = 0;
    }

    return ans;
}