#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
const int dx1[] = {0, 1};
const int dy1[] = {1, 0};
const int dx2[] = {0, 1, 0, -1};
const int dy2[] = {1, 0, -1, 0};
int n, m;
bool a[1005][1005], check[1005][1005], vis[1005][1005];
set<int> s1[1005], s2[1005];
void df1(int x, int y) {
vis[x][y] = 1;
if (a[x][y]) return;
for (int i = 0; i < 2; i++) {
int tx = x + dx1[i], ty = y + dy1[i];
if (tx > n or ty > m) continue;
if (!vis[tx][ty]) df1(tx, ty);
check[x][y] |= check[tx][ty];
}
}
void dfs2(int x, int y, int h1, int w1, int h2, int w2) {
check[x][y] = 0;
s1[y].erase(x), s1[y + 1].erase(x), s2[x].erase(y), s2[x + 1].erase(y);
for (int i = 0; i < 4; i++) {
int tx = x + dx2[i], ty = y + dy2[i];
if (tx > h2 or tx < h1 or ty > w2 or ty > w1 or !check[tx][ty]) continue;
dfs2(tx, ty, h1, w1, h2, w2);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) cin >> a[i][j];
}
vis[n][m] = 1, check[n][m] = 1;
df1(1, 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (check[i][j] and check[i][j - 1]) s1[j].insert(i);
if (check[i][j] and check[i - 1][j]) s2[i].insert(j);
}
}
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
if (!check[x][y]) cout << 1 << "\n";
else {
auto it1 = s1[y].upper_bound(x), it2 = s2[x].upper_bound(y);
if (it1 == s1[y].end() and it2 == s2[x].end()) {
cout << 0 << "\n";
continue;
}
cout << 1 << "\n";
int h1 = x, w1 = y, h2 = x, w2 = y;
for (int i = x - 1; i >= 1; i--) {
if (check[i][y] and !check[i][y + 1]) h1 = i;
else break;
}
for (int i = x + 1; i <= n; i++) {
if (check[i][y] and !check[i][y - 1]) h2 = i;
else break;
}
for (int j = y - 1; j >= 1; j--) {
if (check[x][j] and !check[x + 1][j]) w1 = j;
else break;
}
for (int j = y + 1; y <= m; y++) {
if (check[x][j] and !check[x - 1][j]) w2 = j;
else break;
}
dfs2(x, y, h1, w1, h2, w2);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
