#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
int ma[1010][1010];
int X[5]={0,1,0,-1};
int Y[5]={1,0,-1,0};
int n,m;
bool ar[1010][1010],ab[1010][1010],path[1010][1010];
int num[1000010];
void arriba(){
ar[0][0]=1;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(ar[i][j]){
for(int k=0;k<2;k++){
int xi,yi;
xi=i+X[k]; yi=j+Y[k];
if(xi<n && yi<m && !ma[xi][yi]) ar[xi][yi]=1;
}
}
}
void abajo(){
ab[n-1][m-1]=2;
for(int i=n-1;i>=0;i--)
for(int j=m-1;j>=0;j--)
if(ab[i][j]){
for(int k=2;k<4;k++){
int xi,yi;
xi=i+X[k]; yi=j+Y[k];
if(xi>=0 && yi>=0 && !ma[xi][yi]) ab[xi][yi]=1;
}
}
}
bool check(int a,int b){
if(!path[a][b]) return 1;
if(num[a+b]>1){
path[a][b]=0;
num[a+b]--;
queue<ii> q;
for(int i=0;i<4;i++){
int xi=a+X[i];
int yi=b+Y[i];
if(xi>=0 && xi<n && yi>=0 && yi<m && path[xi][yi]){
q.push(ii(xi,yi));
//cout<<xi<<" "<<yi<<endl;
}
}
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop();
if((x==0 && y==0) || (x==n-1 && y==m-1)) continue;
bool s1=0,s2=0;
for(int i=0;i<2;i++){
int xi,yi;
xi=x+X[i]; yi=y+Y[i];
if(xi<n && yi<m) s1|=path[xi][yi];
}
for(int i=2;i<4;i++){
int xi,yi;
xi=x+X[i]; yi=y+Y[i];
if(xi>=0 && yi>=0) s2|=path[xi][yi];
}
//cout<<x<<" "<<y<<" "<<s1<<" "<<s2<<endl;
if(!s1 || !s2){
//cout<<x<<" "<<y<<endl;
num[x+y]--;
path[x][y]=0;
for(int i=0;i<4;i++){
int xi,yi;
xi=x+X[i]; yi=y+Y[i];
if(xi>=0 && xi<n && yi>=0 && yi<m && path[xi][yi]) q.push(ii(xi,yi));
}
}
}
return 1;
}
else return 0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
memset(num,0,sizeof num);
cin>>n>>m;
for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>ma[i][j];
arriba();
abajo();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
path[i][j]=(ar[i][j] && ab[i][j]);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(path[i][j]) num[i+j]++;
}
}
int q;
cin>>q;
/* for(int j=0;j<n;j++){
for(int k=0;k<m;k++) cout<<path[j][k]<<" ";
cout<<endl;
}*/
for(int i=0;i<q;i++){
int a,b;
cin>>a>>b;
a--; b--;
if(check(a,b)){
cout<<"1\n";
}
else cout<<"0\n";
/*for(int j=0;j<n;j++){
for(int k=0;k<m;k++) cout<<path[j][k]<<" ";
cout<<endl;
}*/
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
