#include <bits/stdc++.h>
using namespace std;
#define invalid(e, f) (min(e, f) < 0 || !min(n-e, m-f) || g[e][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]){
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;
}
void remove(int a, int b){
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) || !inPath[i][j] || v[i][j]) continue;
int s = i - dx[!k], t = j - dy[!k];
if(invalid(s, t) || !inPath[s][t]){
add(i, j);
}
}
}
}
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){
remove(a, b);
++c[a+b];
inPath[a][b] = 1;
dx[0] = dy[1] = -1;
remove(a, b);
dx[0] = dy[1] = 1;
g[a][b] = 1;
}
cout << g[a][b] << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
3 ms |
588 KB |
Output is correct |
4 |
Correct |
4 ms |
588 KB |
Output is correct |
5 |
Correct |
4 ms |
720 KB |
Output is correct |
6 |
Correct |
5 ms |
716 KB |
Output is correct |
7 |
Correct |
5 ms |
716 KB |
Output is correct |
8 |
Correct |
5 ms |
716 KB |
Output is correct |
9 |
Correct |
4 ms |
716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
3 ms |
588 KB |
Output is correct |
4 |
Correct |
4 ms |
588 KB |
Output is correct |
5 |
Correct |
4 ms |
720 KB |
Output is correct |
6 |
Correct |
5 ms |
716 KB |
Output is correct |
7 |
Correct |
5 ms |
716 KB |
Output is correct |
8 |
Correct |
5 ms |
716 KB |
Output is correct |
9 |
Correct |
4 ms |
716 KB |
Output is correct |
10 |
Correct |
13 ms |
716 KB |
Output is correct |
11 |
Correct |
3 ms |
460 KB |
Output is correct |
12 |
Correct |
220 ms |
7824 KB |
Output is correct |
13 |
Correct |
99 ms |
4968 KB |
Output is correct |
14 |
Correct |
359 ms |
12716 KB |
Output is correct |
15 |
Correct |
371 ms |
12960 KB |
Output is correct |
16 |
Correct |
384 ms |
13764 KB |
Output is correct |
17 |
Correct |
400 ms |
14532 KB |
Output is correct |
18 |
Correct |
396 ms |
14180 KB |
Output is correct |
19 |
Correct |
405 ms |
14800 KB |
Output is correct |
20 |
Correct |
397 ms |
15044 KB |
Output is correct |
21 |
Correct |
400 ms |
14916 KB |
Output is correct |