#include <bits/stdc++.h>
void place(int X, int Y, std::queue <std::pair <int, int>>& q, std::vector <int>& le, std::vector <int>& ri, std::vector <std::vector <int>>& g, std::vector <std::vector <int>>& ou, std::vector <std::vector <int>>& in, int n, int m) {
q.push({ X, Y });
while (q.size()) {
auto p = q.front(); q.pop();
int x = p.first, y = p.second;
if (g[x][y]) continue;
g[x][y] = 1;
if (x && !--ou[x - 1][y]) q.push({ x - 1, y });
if (y && !--ou[x][y - 1]) q.push({ x, y - 1 });
if (x + 2 <= n && !--in[x + 1][y]) q.push({ x + 1, y });
if (y + 2 <= m && !--in[x][y + 1]) q.push({ x, y + 2 });
while (le[x + y] == x && g[x][y]) le[x + y]++, x++, y--;
while (ri[x + y] == x && g[x][y]) ri[x + y]--, x--, y++;
}
}
int main() {
std::ios::sync_with_stdio(0); std::cin.tie(0);
int n, m; std::cin >> n >> m;
std::vector <std::vector <int>> g(n, std::vector <int> (m)), ou(g), in(g);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j + 2 <= m) ou[i][j]++, in[i][j + 1]++;
if (i + 2 <= n) ou[i][j]++, in[i + 1][j]++;
}
}
std::vector <int> le(n + m, n), ri(n + m, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
le[i + j] = std::min(le[i + j], i);
ri[i + j] = std::max(ri[i + j], i);
}
}
std::queue <std::pair <int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int p; std::cin >> p;
if (p) place(i, j, q, le, ri, g, ou, in, n, m);
}
}
int k; std::cin >> k;
while (k--) {
int x, y; std::cin >> x >> y; x--, y--;
if (le[x + y] == x && ri[x + y] == x) {
std::cout << "0\n"; continue;
}
std::cout << "1\n";
place(x, y, q, le, ri, g, ou, in, n, m);
}
}
// :D
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
