#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=1005;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll n,m,a[N][N],mnr[N][N],mxr[N][N],mxc[N][N],mnc[N][N],sz[N][N];
pair<ll,ll>pr[N][N];
ll dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
pair<ll,ll> get(pair<ll,ll> a){
ll x,y;
x=a.f;
y=a.s;
return (pr[x][y]==make_pair(x,y) ? make_pair(x,y) : pr[x][y]=get(pr[x][y]));
}
void uni(pair<ll,ll>u,pair<ll,ll>v){
u=get(u);
v=get(v);
if(u==v)return;
if(sz[u.f][u.s]>sz[v.f][v.s])swap(v,u);
pr[u.f][u.s]=v;
sz[v.f][v.s]+=sz[u.f][u.s];
mxc[v.f][v.s]=max(mxc[v.f][v.s],mxc[u.f][u.s]);
mnc[v.f][v.s]=min(mnc[v.f][v.s],mnc[u.f][u.s]);
mxr[v.f][v.s]=max(mxr[v.f][v.s],mxr[u.f][u.s]);
mnr[v.f][v.s]=min(mnr[v.f][v.s],mnr[u.f][u.s]);
}
bool try_uni(ll x,ll y){
ll maxr=x;
ll minr=x;
ll maxc=y;
ll minc=y;
for(ll i=0;i<4;i++){
for(ll j=0;j<4;j++){
if(dx[i]==0&&dy[j]==0)continue;
if(!a[x+dx[i]][y+dy[j]])continue;
pair<ll,ll> nw={x+dx[i],y+dy[j]};
nw=get(nw);
// cout<<mx[2][1]<<'\n';
maxr=max(maxr,mxr[nw.f][nw.s]);
minr=min(minr,mnr[nw.f][nw.s]);
maxc=max(maxc,mxc[nw.f][nw.s]);
minc=min(minc,mnc[nw.f][nw.s]);
}
}
if((maxr==n&&minr==1)||(maxc==m&&minc==1)||(maxr==n&&maxc==m)||(minc==1&&minr==1)){
return 0;
}
mxr[x][y]=x;
mnr[x][y]=x;
mxc[x][y]=y;
mnc[x][y]=y;
for(ll i=0;i<4;i++){
for(ll j=0;j<4;j++){
if(dx[i]==0&&dy[j]==0)continue;
if(!a[x+dx[i]][y+dy[j]])continue;
pair<ll,ll> nw={x+dx[i],y+dy[j]};
nw=get(nw);
if(nw==get({x,y}))continue;
uni(nw,get({x,y}));
}
}
a[x][y]=1;
return 1;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
cin>>a[i][j];
pr[i][j]={i,j};
sz[i][j]=1;
ll x=i;
ll y=j;
mxr[x][y]=x;
mnr[x][y]=x;
mxc[x][y]=y;
mnc[x][y]=y;
}
}for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
if(!a[i][j])continue;
ll x=i;
ll y=j;
for(ll i=0;i<4;i++){
for(ll j=0;j<4;j++){
if(dx[i]==0&&dy[j]==0)continue;
if(!a[x+dx[i]][y+dy[j]])continue;
pair<ll,ll> nw={x+dx[i],y+dy[j]};
nw=get(nw);
if(nw==get({x,y}))continue;
uni(nw,get({x,y}));
}
}
}
}
ll q;
cin>>q;
while(q--){
ll x,y;
cin>>x>>y;
cout<<try_uni(x,y)<<'\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |