/*
IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;
#define SQ 350
#define endl '\n'
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define pf push_front
#define PQ priority_queue
#define size(x) ((ll)x.size())
#define all(x) (x).begin(),(x).end()
#define kill(x) cout << x << '\n', exit(0);
#define set_dec(x) cout << fixed << setprecision(x);
#define ios ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x) cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
const int N = 1005, lg=18;
const ll MOD = 1e9+7; // 998244353
ll getmod(ll a, ll mod=MOD) {return (a>=0&&a<mod ? a : ((a%mod+mod)%mod));}
ll max(ll a, ll b) {return (a>b ? a : b);}
ll min(ll a, ll b) {return (a<b ? a : b);}
ll abso(ll a) {return (a<0?-a:a);}
inline ll poww(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = getmod(ans*a);
b >>= 1;
a = getmod(a*a);
}
return ans;
}
int n, m, q, A[N][N], cnt[N], dp[N][N], pd[N][N], mark[N][N], OK[N][N];
int dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0};
int main () {
ios;
cin>>n>>m;
for(int i=1; i<=n; ++i) {
for(int j=1; j<=m; ++j) {
cin>>mark[i][j];
}
}
for(int i=0;i<N;++i) {
mark[n+1][i]=mark[0][i]=mark[i][m+1]=mark[i][0]=1;
}
pd[n][m]=dp[1][1]=1;
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j){
dp[i][j]|=(dp[i-1][j] && mark[i-1][j]==0 && mark[i][j]==0);
dp[i][j]|=(dp[i][j-1] && mark[i][j-1]==0 && mark[i][j]==0);
}
}
for(int i=n;i;--i) {
for(int j=m;j;--j){
pd[i][j]|=(pd[i+1][j] && mark[i+1][j]==0 && mark[i][j]==0);
pd[i][j]|=(pd[i][j+1] && mark[i][j+1]==0 && mark[i][j]==0);
if(pd[i][j] == dp[i][j] && pd[i][j] == 1) {
OK[i][j]=1;
cnt[i+j]++;
}
}
}
cin>>q;
while(q--) {
int x,y;
cin>>x>>y;
if(cnt[x+y]==1) {
cout<<"0\n";
continue;
}
cout<<"1\n";
if(OK[x][y] == 0){
continue;
}
queue<pii> q;
q.push({x, y});
mark[x][y]=1;
while(!q.empty()) {
pii v = q.front();
q.pop();
cnt[v.F+v.S]--;
dp[v.F][v.S] = pd[v.F][v.S] = OK[v.F][v.S] = 0;
for(int i=0;i<4;++i) {
int a=v.F+dx[i], b=v.S+dy[i];
if(Mp(a,b)==Mp(1,1) || Mp(a,b)==Mp(n,m)) {
continue;
}
if(mark[a][b]==0 && OK[a][b]==1 && ((dp[a-1][b]==0&&dp[a][b-1]==0) || (pd[a+1][b]==0&&pd[a][b+1]==0))) {
dp[a][b]=pd[a][b]=OK[a][b]=0;
q.push({a,b});
}
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5080 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5080 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
