#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e3+7;
int T[LIM][LIM], A[LIM][LIM], B[LIM][LIM], sum[2*LIM], n, m;
void DFS(int a, int b) {
A[a][b]=0;
if(B[a][b]) --sum[a+b];
if(b<m && !A[a-1][b+1] && A[a][b+1]) DFS(a, b+1);
if(a<n && !A[a+1][b-1] && A[b+1][b]) DFS(a+1, b);
}
void DFS2(int a, int b) {
B[a][b]=0;
if(A[a][b]) --sum[a+b];
if(a>1 && !B[a-1][b+1] && B[a-1][b]) DFS2(a-1, b);
if(b>1 && !B[a+1][b-1] && B[a][b-1]) DFS2(a, b-1);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
rep(i, n) rep(j, m) cin >> T[i+1][j+1];
A[1][1]=1;
rep(i, n) rep(j, m) {
if((A[i+1][j] || A[i][j+1]) && !T[i+1][j+1]) A[i+1][j+1]=1;
}
B[n][m]=1;
for(int i=n; i; --i) {
for(int j=m; j; --j) {
if((B[i+1][j] || B[i][j+1]) && !T[i][j]) B[i][j]=1;
if(A[i][j] && B[i][j]) ++sum[i+j];
}
}
int q;
cin >> q;
while(q--) {
int a, b;
cin >> a >> b;
if(sum[a+b]>1 || !A[a][b] || !B[a][b]) {
cout << 1 << '\n';
if(A[a][b]) DFS(a, b);
if(B[a][b]) DFS2(a, b);
} else {
cout << 0 << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1480 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1480 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
