#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n, m, q;
int ar[1005][1005];
int val[1005][1005];
int cnt[2005];
bool change(int x, int y) {
if (val[x][y] == 1) {
return 1;
}
if (cnt[x + y] == 1) {
return 0;
}
stack<pair<int, int>> st;
if (val[x][y] == 0) {
val[x][y] = 1;
cnt[x + y]--;
st.push({x, y});
}
while (!st.empty()) {
int xx = st.top().first;
int yy = st.top().second;
st.pop();
if (val[xx - 1][yy + 1] == 1) {
if (val[xx - 1][yy] == 0) {
val[xx - 1][yy] = 1;
cnt[xx - 1 + yy]--;
st.push({xx - 1, yy});
}
if (val[xx][yy + 1] == 0) {
val[xx][yy + 1] = 1;
cnt[xx + yy + 1]--;
st.push({xx, yy + 1});
}
}
if (val[xx + 1][yy - 1] == 1) {
if (val[xx + 1][yy] == 0) {
val[xx + 1][yy] = 1;
cnt[xx + 1 + yy]--;
st.push({xx + 1, yy});
}
if (val[xx][yy - 1] == 0) {
val[xx][yy - 1] = 1;
cnt[xx + yy - 1]--;
st.push({xx, yy - 1});
}
}
}
return 1;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(val, 1, sizeof val);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> ar[i][j];
val[i][j] = 0;
cnt[i + j]++;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (ar[i][j] == 1) {
change(i, j);
}
}
}
cin >> q;
for (int i = 0; i < q; i++) {
int x, y; cin >> x >> y;
cout << change(x, y) << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8524 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
8624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8524 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
8624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
