#include <bits/stdc++.h>
using namespace std;
#define invalid(i, j) min(x, y) < 0 || !min(n-x, m-y)
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];
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]);
}
}
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;
}
}
queue<pair<int, int>> q;
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){
vector<pair<int, int>> bad;
q.emplace(a, b);
v[a][b] = 1;
while(!q.empty()){
auto [x, y] = q.front(); q.pop();
bad.emplace_back(x, y);
for(int k=0; k<2; ++k){
int i = x + dx[k], j = y + dy[k];
if(invalid(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]){
q.emplace(i, j);
v[i][j] = 1;
}
}
}
for(auto &[i, j] : bad){
inPath[i][j] = 0;
--c[i+j];
v[i][j] = 0;
}
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 |
3 ms |
716 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 |
3 ms |
716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
