#include<bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int n, m;
cin >> n >> m;
int a[n][m];
int up[n][m];
int left[n][m];
bool checked[n][m];
bool v[n][m];
up[0][0]=1;
left[0][0]=1;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
checked[i][j]=0;
left[i][j]=0;
up[i][j]=0;
v[i][j]=0;
bool temp;
cin >> temp;
a[i][j]=!temp;
}
}
queue<pair<int, int>> q;
q.push({0,0});
while(!q.empty()){
int x=q.front().second, y=q.front().first;
q.pop();
if(v[y][x]) continue;
v[y][x]=1;
if(x<m-1&&a[y][x+1]){
if(!up[y][x+1]){
q.push({y, x+1});
}
// if(x+1==0)cout << "BLLLARGHHH";
left[y][x+1]=1;
}
if(y<n-1&&a[y+1][x]){
if(!left[y+1][x]){
q.push({y+1, x});
}
up[y+1][x]=1;
}/*
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cout << a[i][j] << left[i][j] <<up[i][j] <<' ';
}
cout << '\n';
}*/
}
checked[n-1][m-1]=1;
int qe;
cin >> qe;
// vector<int>aaaaaaaaaa;
for(int i = 0; i < qe; i++){
queue<pair<int, pair<int, int>>> forgor;
int x, y;
cin >> y >> x;
if(!a[y-1][x-1]){
cout << "1\n";
continue;
}
queue<pair<int, int>> qu;
qu.push({y-1, x-1});
while(!qu.empty()){
int y1 = qu.front().first, x1=qu.front().second;
//cout << y1 << '-' << x1<< ',';
if(checked[y1][x1]){
checked[y-1][x-1]=1;
int ty=y-1; int tx=x-1;
while((ty==n-1||!a[ty+1][tx])^(tx==m-1||!a[ty][tx+1])){
if(checked[ty][tx]) break;
checked[ty][tx]=1;
if(a[ty+1][tx]) ty++;
else if(a[ty][tx+1]) tx++;
}
while(!forgor.empty()){
int type=forgor.front().first;
int y2=forgor.front().second.first;
int x2=forgor.front().second.second;
if(type==0) a[y2][x2]=1;
if(type==1) left[y2][x2]=1;
if(type==2) up[y2][x2]=1;
forgor.pop();
}
cout << "0\n";
// aaaaaaaaaa.push_back(0);
goto ende;
}
qu.pop();
if(!a[y1][x1]) continue;
a[y1][x1]=0;
forgor.push({0, {y1, x1}});
// cout << x1 << ' ' << a[y1][x1+1] << ' ' << !up[y1][x1+1] << ' '<<left[y1][x1+1] << ',';
if(x1<m-1&&a[y1][x1+1]){
if(!up[y1][x1+1]&&left[y1][x1+1]){
qu.push({y1, x1+1});
}
left[y1][x1+1]=0;
forgor.push({1, {y1, x1+1}});
}
if(y1<n-1&&a[y1+1][x1]){
if(!left[y1+1][x1]&&up[y1+1][x1]){
qu.push({y1+1, x1});
}
up[y1+1][x1]=0;
forgor.push({2, {y1+1, x1}});
}
}
cout << "1\n";
//aaaaaaaaaa.push_back(1);
ende:
continue;
}
/* for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cout << a[i][j] << left[i][j] <<up[i][j] <<' ';
}
cout << '\n';
}
cout <<"\n\n\n";
for(int i = 0; i < aaaaaaaaaa.size(); i++){
cout << aaaaaaaaaa[i] << '\n';
}*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
508 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
5 ms |
468 KB |
Output is correct |
| 6 |
Correct |
4 ms |
468 KB |
Output is correct |
| 7 |
Correct |
4 ms |
604 KB |
Output is correct |
| 8 |
Correct |
4 ms |
468 KB |
Output is correct |
| 9 |
Correct |
5 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
508 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
5 ms |
468 KB |
Output is correct |
| 6 |
Correct |
4 ms |
468 KB |
Output is correct |
| 7 |
Correct |
4 ms |
604 KB |
Output is correct |
| 8 |
Correct |
4 ms |
468 KB |
Output is correct |
| 9 |
Correct |
5 ms |
468 KB |
Output is correct |
| 10 |
Correct |
12 ms |
1240 KB |
Output is correct |
| 11 |
Correct |
3 ms |
468 KB |
Output is correct |
| 12 |
Correct |
227 ms |
15860 KB |
Output is correct |
| 13 |
Correct |
85 ms |
12408 KB |
Output is correct |
| 14 |
Correct |
365 ms |
14264 KB |
Output is correct |
| 15 |
Correct |
336 ms |
15080 KB |
Output is correct |
| 16 |
Execution timed out |
5036 ms |
46292 KB |
Time limit exceeded |
| 17 |
Halted |
0 ms |
0 KB |
- |
