#include <bits/stdc++.h>
using namespace std;
#define invalid(e, f) (min(e, f) < 0 || !min(n-e, m-f))
const int LIM = 1000;
int dx[2] = {-1, 0};
int dy[2] = {0, -1};
int n, m, c[2*LIM];
bool g[LIM][LIM], v[LIM][LIM], inPath[LIM][LIM];
queue<pair<int, int>> q;
void dfs(int x, int y){
if(invalid(x, y) || v[x][y] || g[x][y]){
return;
}else v[x][y] = 1;
for(int k=0; k<2; ++k){
dfs(x + dx[k], y + dy[k]);
}
}
void add(int a, int b){
q.emplace(a, b);
inPath[a][b] = 0;
--c[a+b];
v[a][b] = 1;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
cin >> g[i][j];
dfs(n-1, m-1);
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
inPath[i][j] = v[i][j], v[i][j] = 0;
dx[0] = dy[1] = 1;
dfs(0, 0);
for(int i=0; i<n; ++i){
for(int j=0; j<m; ++j){
if(!v[i][j]) inPath[i][j] = 0;
c[i+j] += inPath[i][j];
v[i][j] = 0;
}
}
int z, a, b; cin >> z;
while(z--){
cin >> a >> b; --a, --b;
if(!inPath[a][b]){
g[a][b] = 1;
}else if(c[a+b] > 1){
add(a, b);
while(!q.empty()){
auto [x, y] = q.front(); q.pop();
v[x][y] = 0;
for(int k=0; k<2; ++k){
int i = x + dx[k], j = y + dy[k];
if(invalid(i, j) || g[i][j] || !inPath[i][j] || v[i][j]) continue;
int s = i - dx[!k], t = j - dy[!k];
if(invalid(s, t) || g[s][t] || !inPath[s][t]){
add(i, j);
}
}
}
g[a][b] = 1;
}
cout << g[a][b] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
