#include <bits/stdc++.h>
#define l long long
using namespace std;
const l LEN = 1005;
l n, m;
array<array<bool, LEN>, LEN> grid;
array<array<bool, LEN>, LEN> possible, visited, updatepossible;
bool dfs(l x, l y) {
if (visited[x][y]) return possible[x][y];
visited[x][y] = true;
if (grid[x][y]) return possible[x][y] = false;
if (x == n && y == m) return possible[x][y] = true;
if (x != n)
if (dfs(x+1, y)) possible[x][y] = true;
if (y != m)
if (dfs(x, y+1)) possible[x][y] = true;
return possible[x][y];
}
bool dfsback(l x, l y) {
if (!updatepossible[x][y]) return false;
if (grid[x][y]) return false;
if (x != n && updatepossible[x+1][y]) return true;
if (y != m && updatepossible[x][y+1]) return true;
updatepossible[x][y] = false;
if (x != 1 && dfsback(x-1, y)) return true;
if (y != 1 && dfsback(x, y-1)) return true;
return false;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> grid[i][j];
dfs(1, 1);
l q, x, y;
bool left, top;
cin >> q;
while (q--) {
cin >> x >> y;
if (!possible[x][y]) {
grid[x][y] = true;
cout << 1 << "\n";
continue;
}
updatepossible = possible;
updatepossible[x][y] = false;
if (x != 1) top = dfsback(x-1, y);
else top = true;
if (y != 1) left = dfsback(x, y-1);
else left = true;
if (top || left) {
if (x != 1 && top) top = dfsback(x-1, y);
if (y != 1 && left) left = dfsback(x, y-1);
}
if (updatepossible[1][1]) {
possible = updatepossible;
grid[x][y] = true;
cout << 1 << "\n";
} else {
cout << 0 << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
2636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
2636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
