#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tiii = tuple<int, int, int>;
using ld = long double;
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mt make_tuple
#define f first
#define s second
template<class T> void maxself(T& x, T y){x = (y > x ? y : x);}
template<class T> void minself(T& x, T y){x = (y < x ? y : x);}
const ld PI = 3.141592653589793238462643;
const ll mod = 1000000007;
struct mi{
ll val;explicit operator int() const {return val;}
mi():val(0){}
mi(ll v):val(v % mod){}
};
mi operator+(mi a, mi b){return (a.val + b.val) % mod;}
mi operator*(mi a, mi b){return (a.val * b.val) % mod;}
mi operator-(mi a, mi b){return (a.val - b.val + mod) % mod;}
const int N = 1000;
int n, m, q, a[N][N], mr[2][N][N], fr[2*N-1];
void cor1(int i, int j) {
if(a[i][j] == 0) return;
int res = 0;
if(i != n - 1 && a[i + 1][j]) res = 1;
if(j != m - 1 && a[i][j + 1]) res = 1;
a[i][j] = res;
if(!res) {
fr[i + j] --;
if(i != 0) cor1(i - 1, j);
if(j != 0) cor1(i, j - 1);
}
}
void cor2(int i, int j) {
if(a[i][j] == 0) return;
int res = 0;
if(i != 0 && a[i - 1][j]) res = 1;
if(j != 0 && a[i][j - 1]) res = 1;
a[i][j] = res;
if(!res) {
fr[i + j] --;
if(i != n - 1) cor2(i + 1, j);
if(j != m - 1) cor2(i, j + 1);
}
}
void solve() {
cin >> n >> m;
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++)
cin >> a[i][j];
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++)
if(i == 0 && j == 0) {
mr[0][i][j] = 1;
} else {
mr[0][i][j] = 0;
if(i > 0 && mr[0][i - 1][j]) mr[0][i][j] = 1;
if(j > 0 && mr[0][i][j - 1]) mr[0][i][j] = 1;
if(a[i][j] == 1) mr[0][i][j] = 0;
}
for(int i = n - 1;i >= 0;i --)
for(int j = m - 1;j >= 0;j --)
if(i == n - 1 && j == m - 1) {
mr[1][i][j] = 1;
} else {
mr[1][i][j] = 0;
if(i < n - 1 && mr[1][i + 1][j]) mr[1][i][j] = 1;
if(j < m - 1 && mr[1][i][j + 1]) mr[1][i][j] = 1;
if(a[i][j] == 1) mr[1][i][j] = 0;
}
for(int i = 0;i < n;i ++) {
for(int j = 0;j < m;j ++) {
a[i][j] = (mr[0][i][j] && mr[1][i][j]);
if(a[i][j]) fr[i + j] ++;
// cerr << a[i][j] << ' ';
}
// cerr << '\n';
}
cin >> q;
while(q --) {
int x, y; cin >> x >> y; x --,y --;
if(a[x][y] == 0) {
cout << 1 << '\n';
continue;
}
if(fr[x + y] == 1) {
cout << 0 << '\n';
} else {
cout << 1 << '\n';
a[x][y] = 0;
fr[x + y] --;
if(x != 0)
cor1(x - 1, y);
if(y != 0)
cor1(x, y - 1);
if(x != n - 1)
cor2(x + 1, y);
if(y != m - 1)
cor2(x, y + 1);
// for(int i = 0;i < n;i ++) {
// for(int j = 0;j < m;j ++)
// cerr << a[i][j] << ' ';
// cerr << '\n';
// }
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while(T --) solve();
}
/*
X if we have a set of blocks which can be part of a path for the coressponding diagnol.
CORRECT mark wether this block can be reached.
CASE 1 :
chaning one can disconnect it it is the only point in the diagnol.
if it is so then do nothing.
CASE 2 :
it can be marked.
use recursive function to check mark other changes.
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1260 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1516 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1516 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1516 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1644 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1772 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1644 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1644 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1260 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1516 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1516 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1516 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1644 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1772 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1644 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1644 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1644 KB |
Output is correct |
| 10 |
Correct |
11 ms |
1388 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 12 |
Correct |
185 ms |
16876 KB |
Output is correct |
| 13 |
Correct |
92 ms |
13420 KB |
Output is correct |
| 14 |
Correct |
364 ms |
20888 KB |
Output is correct |
| 15 |
Correct |
371 ms |
21356 KB |
Output is correct |
| 16 |
Correct |
367 ms |
22252 KB |
Output is correct |
| 17 |
Correct |
380 ms |
23364 KB |
Output is correct |
| 18 |
Correct |
422 ms |
22780 KB |
Output is correct |
| 19 |
Correct |
395 ms |
23788 KB |
Output is correct |
| 20 |
Correct |
336 ms |
23788 KB |
Output is correct |
| 21 |
Correct |
381 ms |
23788 KB |
Output is correct |
