//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define maxn 1005
#define mp 1005*1005
#define ll long long
using namespace std;
int a[maxn][maxn], par[mp + 1];
int find(int x) {
if (par[x] == -1) return -1;
//cout << x << endl;
return x == par[x] ? x : par[x] = find(par[x]);
}
void Union(int x, int y) {
x = find(x), y = find(y);
if (x > y) swap(x, y);
par[find(x)] = find(y);
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0;i < mp;i++) par[i] = -1;
for (int i = 0;i < 4;i++) par[mp - i] = mp -i;
for (int i = 0;i <= m;i++) par[i] = mp;
for (int i = 0;i <= (n + 1) * (m + 2);i+=m + 2) par[i] = mp - 1;
for (int i = m + 1;i < (n + 2) * (m + 2);i += m + 2) par[i] = mp - 3;
for (int i = (n + 1) * (m + 2) + 1;i <= (n + 2) * (m + 2);i++) par[i] = mp - 2;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
cin >> a[i][j];
if (a[i][j] == 1) {
par[i * (m + 2) + j] = i * (m + 2) + j;
for (int x = -1;x <= 1;x++) {
for (int y = -1;y <= 1;y++) {
int nx = x + i, ny = y + j;
//cout << nx << " " << ny << endl;
int num = par[nx * (m + 2) + ny];
//cout << num << endl;
if (num != -1) {
Union(i * (m + 2) + j, nx * (m + 2) + ny);
}
}
}
}
}
}
/*
for (int i = 0;i <= n + 1;i++) {
for (int j= 0;j <= m + 1;j++) cout << par[i * (m + 2) + j] << " ";
cout << endl;
}
*/
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
bool b[4], c[4];
for (int i = 0;i < 4;i++) b[i] = c[i] = false;
for (int i = -1;i <= 1;i++) {
for (int j = -1;j <= 1;j++) {
int nx = x + i, ny = y + j, num = find(nx * (m + 2) + ny);
if (num <= mp && num > mp - 4) c[mp - num] = 1;
}
}
for (int i = 0;i < 4;i++) {
//cout << mp - find(mp - i) << endl;
b[i] = c[mp - find(mp - i)];
//cout << c[i];
}
//cout << endl;
if ((b[0] && b[2]) || (b[1] && b[3]) || (b[0] && b[1]) || (b[2] && b[3])) {
cout << 0 << "\n";
} else {
cout << 1 << "\n";
par[x * (m + 2) + y] = x * (m + 2) + y;
for (int i = -1;i <= 1;i++) {
for (int j = -1;j <= 1;j++) {
int nx = x + i, ny = y + j, num = par[nx * (m + 2) + ny];
if (num != -1) {
Union(x * (m + 2) + y, num);
}
}
}
}
}
}
/*
23 001 000 3
22 21 12
2 3
0 0 1
0 0 0
3
2 2
2 1
1 2
2 2
0 0
0 0
3
1 2
2 1
2 1
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4588 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
4716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4588 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
4716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
