#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vb = vector<bool>;
#define all(v) begin(v), end(v)
const int N = 1e3 + 5;
using bs = bitset<N>;
struct grid {
int n, m;
int tp;
bs blocked[N], vis[N], on_path[N];
grid() {}
grid(int _n, int _m, int _tp, bs _blocked[N]) : n(_n), m(_m), tp(_tp) {
for(int i = 1; i <= n; ++i) {
blocked[i] = _blocked[i];
}
if(tp) {
swap(n, m);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
int x = blocked[i][j], y = blocked[j][i];
blocked[j][i] = x, blocked[i][j] = y;
}
}
}
find_least_path(1, 1);
}
bool find_least_path(int x, int y) {
if(x > n or y > m) return 0;
if(blocked[x][y]) return vis[x][y] = 1, 0;
if(x == n and y == m) {
on_path[x][y] = 1;
return 1;
}
if(!vis[x][y+1] and find_least_path(x, y+1)) {
on_path[x][y] = 1;
return 1;
}
if(!vis[x+1][y] and find_least_path(x+1, y)) {
on_path[x][y] = 1;
return 1;
}
vis[x][y] = 1;
return 0;
}
void destroy(int x, int y) {
if(tp) swap(x, y);
blocked[x][y] = 1;
if(!on_path[x][y]) return;
for(int i = 1; i <= n; ++i) {
vis[i].reset(), on_path[i].reset();
}
find_least_path(1, 1);
}
int fn(int x, int y) {
if(tp) swap(x, y);
return on_path[x][y];
}
};
int main(int argc, char const *argv[])
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int n, m;
scanf("%d %d", &n, &m);
grid g[2];
bs blocked[N];
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
int x;
scanf("%d", &x);
blocked[i][j] = x;
}
}
for(int i : {0, 1}) {
g[i] = grid(n, m, i, blocked);
}
int q; scanf("%d", &q);
while(q--) {
int x, y;
scanf("%d %d", &x, &y);
if(g[0].fn(x, y) and g[1].fn(x, y)) {
puts("0");
} else {
puts("1");
for(int i : {0, 1}) {
g[i].destroy(x, y);
}
}
}
return 0;
}
Compilation message
furniture.cpp: In function 'int main(int, const char**)':
furniture.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
71 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:77:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
77 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
furniture.cpp:84:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | int q; scanf("%d", &q);
| ~~~~~^~~~~~~~~~
furniture.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
87 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1536 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
