#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
const int N = 1003;
int n, m;
bool c[N][N];
int id[3][N][N];
bool blocked[N][N];
int adjblocked[2][N][N];
vector<vector<int>> dx, dy;
pair<int, int> cell[3][N + N];
void dfs(int s, int x, int y) {
//assert(id[s][x][y] != -1);
for (int k = 0; k < 2; ++k) {
int nx = x + dx[s][k], ny = y + dy[s][k];
if (id[s][nx][ny] != -1 || nx > n || ny > m) {
continue;
}
if (!blocked[nx][ny]) {
id[s][nx][ny] = id[s][x][y] + 1;
cell[s][id[s][nx][ny]] = {nx, ny};
return dfs(s, nx, ny);
}
}
}
pair<int, int> bfs(int s, int sx, int sy) {
queue<pair<int, int>> que;
que.emplace(sx, sy);
int mn = n + m, mx = 0;
while (!que.empty()) {
auto [x, y] = que.front();
que.pop();
if (id[s][x][y] != -1) {
mx = max(mx, id[s][x][y]);
mn = min(mn, id[s][x][y]);
id[s][x][y] = -1;
}
blocked[x][y] = true;
for (int k = 0; k < 4; ++k) {
int nx = x + dx[2][k], ny = y + dy[2][k];
if (nx <= 0 || ny <= 0 || nx > n || ny > m) continue;
adjblocked[(k / 2) ^ 1][nx][ny]++;
if (adjblocked[(k / 2) ^ 1][nx][ny] == 2 && !blocked[nx][ny]) {
que.emplace(nx, ny);
}
}
}
return make_pair(mn, mx);
}
bool edit(int x, int y) {
if (blocked[x][y]) return true;
if (id[0][x][y] != -1 && id[1][x][y] != -1) return false;
int s = (id[0][x][y] != -1 ? 0 : id[1][x][y] != -1 ? 1 : 2);
auto [mn, mx] = bfs(s, x, y);
if (s == 2) {
//assert(mn == -1 && mx == -1);
return true;
}
auto [sx, sy] = cell[s][mn - 1];
dfs(s, sx, sy);
return true;
}
void init() {
dx.resize(3);
dy.resize(3);
dx[0] = {1, 0}; dy[0] = {0, 1};
dx[1] = {0, 1}; dy[1] = {1, 0};
dx[2] = {1, 0, -1, 0}; dy[2] = {0, 1, 0, -1};
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if ((i == 1 && j == 1) || (i == n && j == m)) continue;
for (int k = 0; k < 4; ++k) {
int ni = i + dx[2][k], nj = j + dy[2][k];
if (ni < 1 || ni > n || nj < 1 || nj > m) {
adjblocked[k / 2][i][j]++;
}
}
}
}
memset(id, -1, sizeof id);
id[0][1][1] = id[1][1][1] = 1;
id[0][n][m] = id[1][n][m] = n + m - 1;
cell[0][1] = cell[1][1] = {1, 1};
cell[0][n + m - 1] = cell[1][n + m - 1] = {n, m};
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (c[i][j] == 1) {
bfs(2, i, j);
}
}
}
dfs(0, 1, 1);
dfs(1, 1, 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> c[i][j];
}
}
init();
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
bool ok = edit(x, y);
cout << ok << '\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
19032 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
21084 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
19032 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
21084 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
