#include "labirintus.h"
#include <bits/stdc++.h>

using namespace std;

int r,c;
vector<vector<int> > h;
vector<vector<int> > w;
int tim=1;
bool prop[1000001];
vector<int> t[1000001]; 
vector<int> d;

void fill(int x,int y) {
    if ((!((x>=0) && (x<r) && (y>=0) && (y<c))) || (h[x][y]!=0)) {
        return;
    }
    h[x][y]=tim;
    fill(x+1,y);
    fill(x-1,y);
    fill(x,y+1);
    fill(x,y-1);
}

void init_labyrinth(int R, int C, std::vector<std::vector<int>> L) {
    h=L; w=L;
    r=R; c=C;
    for (int i=0;i<r;i++) {
        for (int j=0;j<c;j++) {
            h[i][j]=0;
        }
    }
    for (int i=0;i<r;i++) {
        for (int j=0;j<c;j++) {
            if ((L[i][j]==1) && (h[i][j]==0)) {
                fill(i,j);
                tim++;
            }
            if (L[i][j]==0) {
                h[i][j]=tim;
                tim++;
            }
        }
    }
    for (int i=1;i<c;i++) {
        prop[h[0][i]]=1;
    }
    for (int i=0;i<r;i++) {
        prop[h[i][c-1]]=1;
    }
    return;
}

int db=1;
int volt[1000001];
bool ans=0;

void dfs(int p) {
    volt[p]=db;
    for (int i:t[p]) {
        if (volt[i]!=db) {
            dfs(volt[i]);
        }
    }
    ans=ans||prop[p];
}

bool can_escape(int N, std::vector<int> U, std::vector<int> V) {
    ans=0;
    for (int i=0;i<N;i++) {
        if ((U[i] < r-1) && (h[U[i]][V[i]]!=h[U[i]+1][V[i]]) && (w[U[i]+1][V[i]]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]+1][V[i]]);
            t[h[U[i]+1][V[i]]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]+1][V[i]]);
        }
        if ((V[i] < c-1) && (h[U[i]][V[i]]!=h[U[i]][V[i]+1]) && (w[U[i]][V[i]+1]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]][V[i]+1]);
            t[h[U[i]][V[i]+1]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]+1]);
        }
        if ((U[i] > 0) && (h[U[i]][V[i]]!=h[U[i]-1][V[i]]) && (w[U[i]-1][V[i]]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]-1][V[i]]);
            t[h[U[i]-1][V[i]]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]-1][V[i]]);
        }
        if ((V[i] > 0) && (h[U[i]][V[i]]!=h[U[i]][V[i]-1]) && (w[U[i]][V[i]-1]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]][V[i]-1]);
            t[h[U[i]][V[i]-1]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]-1]);
        }
        w[U[i]][V[i]]=1;
    }
    for (int i=1;i<r;i++) {
        if (volt[h[i][0]]!=db) {
            dfs(h[i][0]);
        }
    }
    for (int i=0;i<c;i++) {
        if (volt[h[r-1][i]]!=db) {
            dfs(h[r-1][i]);
        }
    }
    for (int i=0;i<N;i++) {
        w[U[i]][V[i]]=0;
    }
    for (int i:d) {
        t[i].clear();
    }
    db++;
    return(ans);
}