#include <bits/stdc++.h>
#define fastio ios_base :: sync_with_stdio(0), cin.tie(0);
using namespace std;
using ll = long long;
const int mxN = 1e3 + 5, mod = 1e9 + 7;
int n, m, a[mxN][mxN];
bool dp[mxN][mxN], s[mxN][mxN];
bool can(int i, int j) {
return (dp[i][j] & s[i][j]);
}
int main() {
fastio;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) cin >> a[i][j];
}
dp[1][1] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1 + (i == 1); j <= m; ++j) {
if (a[i][j]) continue;
dp[i][j] = (dp[i - 1][j] | dp[i][j - 1]);
}
}
s[n][m] = 1;
for (int i = n; i > 0; i--) {
for (int j = m - (i == n); j > 0; j--) {
if (a[i][j])
continue;
s[i][j] = (s[i + 1][j] | s[i][j + 1]);
}
}
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
if (can(x + 1, y - 1) || can(x - 1, y + 1)) {
cout << "1\n";
a[x][y] = 1;
if (dp[x][y]) {
queue <pair <int, int> > q;
dp[x][y] = 0;
q.push({x, y});
vector <pair <int, int> > add;
while (!q.empty()) {
int i = q.front().first;
int j = q.front().second;
q.pop();
if (!a[x][y] && (dp[i - 1][j] | dp[i][j - 1])) {
dp[i][j] = 1;
add.push_back({i, j});
continue;
}
if (i + 1 < n && dp[i + 1][j]) {
dp[i + 1][j] = 0;
q.push({i + 1, j});
}
if (j + 1 < m && dp[i][j + 1]) {
dp[i][j + 1] = 0;
q.push({i, j + 1});
}
}
for (auto [i, j] : add) {
if ((dp[i - 1][j] | dp[i][j - 1]))
dp[i][j] = 1;
}
}
if (s[x][y]) {
queue <pair <int, int> > q;
s[x][y] = 0;
q.push({x, y});
vector <pair <int, int> > add;
while (!q.empty()) {
int i = q.front().first;
int j = q.front().second;
q.pop();
if ((s[i + 1][j] | s[i][j + 1])) {
s[i][j] = 1;
add.push_back({i, j});
continue;
}
if (i > 1 && s[i - 1][j]) {
s[i - 1][j] = 0;
q.push({i - 1, j});
}
if (j > 1 && s[i][j - 1]) {
s[i][j - 1] = 0;
q.push({i, j - 1});
}
}
for (auto [i, j] : add) {
if ((s[i + 1][j] | s[i][j + 1]))
s[i][j] = 1;
}
}
}
else
cout << "0\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
