#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
const int N = 1e3 + 5;
int a[N][N], used[N][N], cnt[N + N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
cnt[i + j]++;
}
}
int ch[6][2] = {
{0, 1},
{-1, 0},
{-1, 1},
{1, 0},
{0, -1},
{1, -1}
};
auto check = [&](int i, int j){
queue<ar<int, 2>> qq;
used[i][j] = 1;
qq.push({i, j});
auto check = [&](int i, int j) { return (1 <= i && i <= n && 1 <= j && j <= m); };
while(!qq.empty()){
auto u = qq.front(); qq.pop();
cnt[u[0] + u[1]]--;
for(int t=0;t<6;t+=3){
int x = u[0] + ch[t+2][0], y = u[1] + ch[t+2][1];
if(!check(x, y) || used[x][y]){
int i = u[0] + ch[t][0], j = u[1] + ch[t][1];
if(check(i, j) && !used[i][j]){
used[i][j] = 1, qq.push({i, j});
} i = u[0] + ch[t+1][0], j = u[1] + ch[t+1][1];
if(check(i, j) && !used[i][j]){
used[i][j] = 1, qq.push({i, j});
}
}
}
}
};
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]) check(i, j);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
assert(cnt[i + j] > 0);
}
}
int q; cin>>q;
while(q--){
//~ for(int i=1;i<=n;i++){
//~ for(int j=1;j<=m;j++){
//~ cout<<used[i][j]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
int i, j; cin>>i>>j;
if(used[i][j]){
cout<<1<<"\n";
continue;
}
if(cnt[i + j] == 1){
cout<<0<<"\n";
continue;
}
check(i, j);
cout<<1<<"\n";
}
//~ for(int i=1;i<=n;i++){
//~ for(int j=1;j<=m;j++){
//~ cout<<used[i][j]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
}
/*
5
5
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
9
1 5
5 1
3 3
1 2
2 2
4 3
4 5
1 4
3 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
2252 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
2252 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
