#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
int ma[1010][1010];
int X[3]={0,1},XI[3]={0,-1};
int Y[3]={1,0},YI[3]={-1,0};
int n,m;
int vis[1010][1010];
int num[1000010];
void arriba(){
vis[0][0]=1;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(vis[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]) vis[xi][yi]=1;
}
}
}
void abajo(){
vis[n-1][m-1]=2;
for(int i=n-1;i>=0;i--)
for(int j=m-1;j>=0;j--)
if(vis[i][j]==2){
for(int k=0;k<2;k++){
int xi,yi;
xi=i+XI[k]; yi=j+YI[k];
if(xi>=0 && yi>=0 && !ma[xi][yi] && vis[xi][yi]) vis[xi][yi]=2;
}
}
}
bool check(int a,int b){
if(vis[a][b]<=1) return 1;
if(num[a+b]>=2) {
num[a+b]--;
return 1;
}
else return 0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
memset(vis,0,sizeof vis);
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++){
if(vis[i][j]==2) num[i+j]++;
}
}
int q;
cin>>q;
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";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4556 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4556 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
