#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, m, cur, cnt;
vector<vector<bool>> v;
vector<bool> block;
vector<int> ff, ls;
vector<vector<bool>> aa, bb;
int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy[8] = {1, -1, 0, 1, -1, 0, 1, -1};
bool check1(int x, int y){
cnt = 0;
if(!block[x]){
if(x == 0) cnt++;
else if(max(y, ls[x]) >= ff[x-1]-1) cnt++;
}
if(x+1 < n && !block[x+1]){
if(ls[x+1] >= min(y, ff[x])-1) cnt++;
}
if(cur-cnt <= 0) return 0;
return 1;
}
bool check2(int x, int y){
bool b1 = 0, b2 = 0;
if(x == n-1) b1 = 1;
if(y == m-1) b2 = 1;
for(int i = 0; i < 8; i++){
int xx = x+dx[i], yy = y+dy[i];
if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
b1|=aa[xx][yy];
b2|=bb[xx][yy];
}
return !(b1&b2);
}
void do2(int x, int y){
bool b1 = 0, b2 = 0;
if(x == n-1) b1 = 1;
if(y == m-1) b2 = 1;
for(int i = 0; i < 8; i++){
int xx = x+dx[i], yy = y+dy[i];
if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
b1|=aa[xx][yy];
b2|=bb[xx][yy];
}
aa[x][y] = b1;
bb[x][y] = b2;
}
void do1(int x, int y){
if(!block[x]){
if(x == 0) block[x] = 1;
else if(max(y, ls[x]) >= ff[x-1]-1) block[x] = 1;
}
if(x+1 < n && !block[x+1]){
if(ls[x+1] >= min(y, ff[x])-1) block[x+1] = 1;
}
ff[x] = min(ff[x], y);
ls[x] = max(ls[x], y);
cur-=cnt;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
v = vector<vector<bool>>(n, vector<bool>(m, 0));
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
bool bl; cin >> bl;
v[i][j] = bl;
}
ff.resize(n, m+1), ls.resize(n, -1);
block.resize(n, 0);
aa = vector<vector<bool>>(n, vector<bool>(m, 0)), bb = aa;
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
if(!v[i][j]) continue;
ff[i] = min(ff[i], j);
ls[i] = max(ls[i], j);
if(i == 0 && !block[i]) block[i] = 1;
else if(j >= ff[i-1]-1) block[i] = 1;
}
for(int j = 0; j < m; j++) if(v[n-1][j]) aa[n-1][j] = 1;
for(int i = 0; i < n; i++) if(v[i][m-1]) bb[i][m-1] = 1;
for(int i = n-2; i >= 0; i--){
for(int j = 0; j < m; j++){
if(!v[i][j]) continue;
if(aa[i+1][j]) aa[i][j] = 1;
if(j > 0 && aa[i+1][j-1]) aa[i][j] = 1;
if(j < m-1 && aa[i+1][j+1]) aa[i][j] = 1;
if(j > 0 && aa[i][j-1]) aa[i][j] = 1;
if(j < m-1 && aa[i][j+1]) aa[i][j] = 1;
}
for(int j = m-1; j >= 0; j--){
if(!v[i][j]) continue;
if(aa[i+1][j]) aa[i][j] = 1;
if(j > 0 && aa[i+1][j-1]) aa[i][j] = 1;
if(j < m-1 && aa[i+1][j+1]) aa[i][j] = 1;
if(j > 0 && aa[i][j-1]) aa[i][j] = 1;
if(j < m-1 && aa[i][j+1]) aa[i][j] = 1;
}
}
for(int j = m-2; j >= 0; j--){
for(int i = 0; i < n; i++){
if(!v[i][j]) continue;
if(bb[i][j+1]) bb[i][j] = 1;
if(i > 0 && bb[i-1][j+1]) bb[i][j] = 1;
if(i < n-1 && bb[i+1][j+1]) bb[i][j] = 1;
if(i > 0 && bb[i-1][j]) bb[i][j] = 1;
if(i < n-1 && bb[i+1][j]) bb[i][j] = 1;
}
for(int i = n-1; i >= 0; i--){
if(!v[i][j]) continue;
if(bb[i][j+1]) bb[i][j] = 1;
if(i > 0 && bb[i-1][j+1]) bb[i][j] = 1;
if(i < n-1 && bb[i+1][j+1]) bb[i][j] = 1;
if(i > 0 && bb[i-1][j]) bb[i][j] = 1;
if(i < n-1 && bb[i+1][j]) bb[i][j] = 1;
}
}
cur = n;
for(int i = 0; i < n; i++) if(block[i]) cur--;
int q; cin >> q;
while(q--){
int x, y; cin >> x >> y; x--, y--;
if(!check1(x, y) || !check2(x, y)){
cout << "0\n";
continue;
}
cout << "1\n";
do1(x, y);
do2(x, y);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
