//Be Name Khoda
#include<bits/stdc++.h>
//pragma shayad niaz she
using namespace std;
typedef long long ll;
typedef long double ld;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()
const ll mxn = 1e3 + 16;
ll n, m, t, q, w;
ll sum[2 * mxn];
bool exist[mxn][mxn], path[mxn][mxn], path2[mxn][mxn];
void DFS(int i, int j) {
path[i][j] = 1;
if(i > 1) {
if(!path[i - 1][j] && !exist[i - 1][j]) {
DFS(i - 1, j);
}
}
if(j > 1) {
if(!path[i][j - 1] && !exist[i][j - 1]) {
DFS(i, j - 1);
}
}
}
void DFS2(int i, int j) {
path2[i][j] = 1;
if(path[i][j]) sum[i + j]++;
if(i < n) {
if(!path2[i + 1][j] && !exist[i + 1][j]) {
DFS2(i + 1, j);
}
}
if(j < m) {
if(!path2[i][j + 1] && !exist[i][j + 1]) {
DFS2(i, j + 1);
}
}
}
void BFS(int q, int w) {
if(!path[q][w]) return;
vector<pii> bfs;
int ptr = 0, i, j;
bfs.push_back({q, w});
while(ptr < int(bfs.size())) {
auto x = bfs[ptr++];
i = x.first, j = x.second;
if(!path[i][j]) continue;
path[i][j] = 0;
if(path2[i][j]) sum[i + j]--;
if(i > 1) {
if(path[i - 1][j] && !path[i - 1][j + 1]) {
bfs.push_back({i - 1, j});
}
} if(j > 1) {
if(path[i][j - 1] && !path[i + 1][j - 1]) {
bfs.push_back({i, j - 1});
}
}
} return;
}
void BFS2(int q, int w) {
if(!path2[q][w]) return;
vector<pii> bfs;
int ptr = 0, i, j;
bfs.push_back({q, w});
while(ptr < int(bfs.size())) {
auto x = bfs[ptr++];
i = x.first, j = x.second;
if(!path2[i][j]) continue;
path2[i][j] = 0;
if(path[i][j]) sum[i + j]--;
if(i < n) {
if(path2[i + 1][j] && !path2[i + 1][j - 1]) {
bfs.push_back({i + 1, j});
}
} if(j < m) {
if(path2[i][j + 1] && !path2[i - 1][j + 1]) {
bfs.push_back({i, j - 1});
}
}
} return;
}
void input() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> exist[i][j];
}
} cin >> t;
}
void solve() {
DFS(n, m);
DFS2(1, 1);
for(int tt = 0; tt < t; tt++) {
cin >> q >> w;
if(!path[q][w] && !path2[q][w]) {
cout << "1\n";
continue;
}
if(!path[q][w] && path2[q][w]) {
cout << "1\n";
BFS2(q, w);
continue;
}
if(path[q][w] && !path2[q][w]) {
cout << "1\n";
BFS(q, w);
continue;
}
if(sum[q + w] == 1) {
cout << "0\n";
continue;
}
if(sum[q + w] > 1) {
cout << "1\n";
BFS(q, w), BFS2(q, w);
}
}
return;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
input(), solve();
return 0;
}
/*
2 3
0 0 1
0 0 0
3
2 2
2 1
1 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
