#include <bits/stdc++.h>
#define l long long
using namespace std;
const l LEN = 1005;
l n, m;
array<bitset<LEN>, LEN> grid;
array<bitset<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;
bool isval = false;
if (x != 1 && dfsback(x-1, y)) isval = true;
if (y != 1 && dfsback(x, y-1)) isval = true;
return isval;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
l a;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> a;
grid[i][j] = a;
}
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) dfsback(x-1, y);
if (y != 1) dfsback(x, y-1);
if (x != 1) dfsback(x-1, y);
// 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;
}
/*
6 8
0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0
0 1 0 0 1 1 1 0
0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
100
4 6
1 2
6 1
5 1
4 1
3 1
2 1
6 2
6 3
4 3
4 4
4 8
5 8
6 8
0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0
0 1 0 0 1 1 1 0
0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
100
6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
100
2 2
1
3 2
1
4 2
1
5 2
1
5 1
1
4 1
1
3 1
1
2 1
1
1 4
1
2 4
1
2 5
1
1 5
1
4 4
1
3 3
0
4 5
1
5 4
1
5 5
0
*/
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:56:10: warning: unused variable 'left' [-Wunused-variable]
56 | bool left, top;
| ^~~~
furniture.cpp:56:16: warning: unused variable 'top' [-Wunused-variable]
56 | bool left, top;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
604 KB |
Output is correct |
| 2 |
Correct |
3 ms |
604 KB |
Output is correct |
| 3 |
Correct |
6 ms |
744 KB |
Output is correct |
| 4 |
Correct |
9 ms |
604 KB |
Output is correct |
| 5 |
Correct |
14 ms |
600 KB |
Output is correct |
| 6 |
Correct |
19 ms |
748 KB |
Output is correct |
| 7 |
Correct |
10 ms |
604 KB |
Output is correct |
| 8 |
Correct |
34 ms |
752 KB |
Output is correct |
| 9 |
Correct |
17 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
604 KB |
Output is correct |
| 2 |
Correct |
3 ms |
604 KB |
Output is correct |
| 3 |
Correct |
6 ms |
744 KB |
Output is correct |
| 4 |
Correct |
9 ms |
604 KB |
Output is correct |
| 5 |
Correct |
14 ms |
600 KB |
Output is correct |
| 6 |
Correct |
19 ms |
748 KB |
Output is correct |
| 7 |
Correct |
10 ms |
604 KB |
Output is correct |
| 8 |
Correct |
34 ms |
752 KB |
Output is correct |
| 9 |
Correct |
17 ms |
604 KB |
Output is correct |
| 10 |
Correct |
13 ms |
600 KB |
Output is correct |
| 11 |
Correct |
10 ms |
748 KB |
Output is correct |
| 12 |
Correct |
837 ms |
2816 KB |
Output is correct |
| 13 |
Correct |
84 ms |
2824 KB |
Output is correct |
| 14 |
Correct |
904 ms |
10320 KB |
Output is correct |
| 15 |
Correct |
1123 ms |
10740 KB |
Output is correct |
| 16 |
Correct |
1312 ms |
11604 KB |
Output is correct |
| 17 |
Correct |
4448 ms |
12024 KB |
Output is correct |
| 18 |
Correct |
2388 ms |
11928 KB |
Output is correct |
| 19 |
Correct |
310 ms |
12492 KB |
Output is correct |
| 20 |
Correct |
900 ms |
12620 KB |
Output is correct |
| 21 |
Correct |
2003 ms |
12400 KB |
Output is correct |
