#include <bits/stdc++.h>
#define maxn 1005
#define fi first
#define se second
using namespace std;
typedef pair<int, int> ii;
int n, m, q;
int a[maxn][maxn];
int cnt[maxn+maxn];
int e[maxn][maxn];
int dv[] = {0, 1};
int dh[] = {1, 0};
int Dv[] = {0, 1, 0, -1};
int Dh[] = {1, 0, -1, 0};
void bfs() {
queue<ii> q;
q.push({1, 1});
vector<vector<bool> > V1(n+1, vector<bool>(m+1, false)); V1[1][1] = true;
while (!q.empty()) {
auto [u, v] = q.front(); q.pop();
for (int k = 0; k < 2; k++) {
int i = u + dv[k], j = v + dh[k];
if (a[i][j] || V1[i][j]) continue;
V1[i][j] = true; q.push({i, j});
}
}
q.push({n, m});
vector<vector<bool> > V2(n+1, vector<bool>(m+1, false)); V2[n][m] = true;
while (!q.empty()) {
auto [u, v] = q.front(); q.pop();
for (int k = 0; k < 2; k++) {
int i = u - dv[k], j = v - dh[k];
if (a[i][j] || V2[i][j]) continue;
V2[i][j] = true; q.push({i, j});
}
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
e[i][j] = (V1[i][j]&V2[i][j]);
}
}
bool check(int x, int y) {
if (x == 1 && y == 1) return false;
if (x == n && y == m) return false;
return ((a[x-1][y] && a[x][y-1]) || (a[x+1][y] && a[x][y+1]));
}
void damnfs(int x, int y) {
queue<ii> q;
q.push({x, y});
while (!q.empty()) {
auto [u, v] = q.front(); q.pop();
for (int k = 0; k < 4; k++) {
int i = u + dv[k], j = v + dh[k];
if (a[i][j]) continue;
if (!e[i][j]) continue;
if (check(i, j)) {
e[i][j] = 0;
--cnt[i+j];
q.push({i, j});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i <= n+1; i++) for (int j = 0; j <= m+1; j++) a[i][j] = 1;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
bfs();
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (e[i][j]) ++cnt[i+j];
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
if (a[x][y]) {
cout << "0\n";
continue;
}
if (!e[x][y]) {
cout << "1\n";
a[x][y] = 1;
continue;
}
if (cnt[x+y] == 1) {
cout << "0\n";
continue;
}
cout << "1\n";
a[x][y] = 1;
e[x][y] = 0;
--cnt[x+y];
damnfs(x, y);
}
}
Compilation message
furniture.cpp: In function 'void bfs()':
furniture.cpp:28:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
28 | auto [u, v] = q.front(); q.pop();
| ^
furniture.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
38 | auto [u, v] = q.front(); q.pop();
| ^
furniture.cpp: In function 'void damnfs(int, int)':
furniture.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | auto [u, v] = q.front(); q.pop();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1624 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1624 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
