# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=1005;
long long n,m,fix[3][N][N],x,y,a,b,aa[N][N],mp[3*N],r[N][N],qq;
queue< pair <int ,int > > q;
int check1(int x, int y) {
if((y==1 ||r[x][y-1]==1) && (x==1 || r[x-1][y]==1))
return 1;
else return 0;
}
int check(int x, int y) {
if (x>n || y>m || x<1 || y<1) return 0;
else return 1;
}
void go(int a, int b, int ty) {
if (fix[ty+1][a][b]==1) return;
fix[ty+1][a][b]=1;
if (check(a+ty,b) && aa[a+ty][b]==0) go(a+ty,b,ty);
if (check(a,ty+b) && aa[a][ty+b]==0 ) go(a,ty+b,ty);
}
void update1(int a, int b) {
while(!q.empty())
q.pop();
x=a;
y=b;
if (r[x+1][y]!=1 && check(x+1, y) && check1(x+1,y)) {
q.push({x+1,y});
r[x+1][y]=1;
mp[x+y+1]--;
}
if (r[x][y+1]!=1 && check(x, y+1) && check1(x,y+1)) {
q.push({x,y+1});
r[x][y+1]=1;
mp[x+y+1]--;
}
while (!q.empty()) {
x=q.front().f;
y=q.front().s;
q.pop();
if (r[x][y] || !check1(x,y)) continue;
if (check(x+1, y)) {
q.push({x+1,y});
}
if (check(x, y+1)) {
q.push({x,y+1});
}
}
}
void update2(int a, int b) {
while(!q.empty())
q.pop();
x=a;
y=b;
if (r[x-1][y]!=1 && check(x-1, y) && check1(x-1,y)) {
q.push({x-1,y});
r[x-1][y]=1;
mp[x+y-1]--;
}
if (r[x][y-1]!=1 && check(x, y-1) && check1(x,y-1)) {
q.push({x,y-1});
r[x][y-1]=1;
mp[x+y-1]--;
}
while (!q.empty()) {
x=q.front().f;
y=q.front().s;
q.pop();
if (r[x][y] || !check1(x,y)) continue;
if (check(x-1, y)) {
q.push({x-1,y});
}
if (check(x, y-1)) {
q.push({x,y-1});
}
}
}
int main() {
cin>>n>>m;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
cin>>aa[i][j];
}
}
go(1,1,1);
go(n,m,-1);
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
if (fix[0][i][j] && fix[2][i][j]) {
r[i][j]=0;
mp[i+j]++;
} else r[i][j]=1;
// cout<<r[i][j]<<" ";
}
//cout<<endl;
}
cin>>qq;
for (int i=1; i<=qq; i++) {
cin>>x>>y;
if (r[x][y]==1) {
cout<<1<<endl;
continue;
}
if (mp[x+y]==1) {
cout<<0<<endl;
continue;
}
cout<<1<<endl;
mp[x+y]--;
r[x][y]=1;
update1(x,y);
update2(x,y);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1612 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
2064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1612 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
2064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
