#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<vector<bool>> p(n+2, vector<bool>(m+2, 0));
vector<vector<bool>> rp(n+2, vector<bool>(m+2, 0));
vector<vector<int>> inp(n+2, vector<int>(m+2, 0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++ ){
cin >> inp[i][j];
}
}
rp[n][m] = 1;
p[1][1] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++ ){
if(inp[i][j] == 0){
if(i!=1 || j!=1)
p[i][j] = p[i-1][j] || p[i][j-1];
}
}
}
for(int i = n; i >0; i--){
for(int j = m; j >0; j-- ){
if(inp[i][j] == 0){
if(i!=n || j!=m)
rp[i][j] = rp[i+1][j] || rp[i][j+1];
}
}
}
int q;
cin >> q;
for(int _ = 0; _ < q; _++){
int x, y;
cin >> x >> y;
if(p[x][y]){
bool canwe = 0;
for(int i = 1; i < x; i++){
if(rp[i][y+1] && p[i][y+1])
{
canwe=1;
}
}
for(int i = x+1; i <= n; i++){
if(rp[i][y-1] && p[i][y-1])
{
canwe=1;
}
}
if(!canwe){
cout << "0\n";
continue;
}
cout << "1\n";
p[x][y] = 0;
stack<pair<int, int>> pos;
pos.push({x+1, y});
pos.push({x, y+1});
while(!pos.empty()){
auto v = pos.top();
pos.pop();
if(p[v.first][v.second]){
p[v.first][v.second] = p[v.first-1][v.second] || p[v.first][v.second-1];
if(!p[v.first][v.second]){
pos.push({v.first+1, v.second});
pos.push({v.first, v.second+1});
}
}
}
rp[x][y] = 0;
stack<pair<int, int>> rpos;
rpos.push({x-1, y});
rpos.push({x, y-1});
while(!pos.empty()){
auto v = rpos.top();
rpos.pop();
if(rp[v.first][v.second]){
rp[v.first][v.second] = rp[v.first+1][v.second] || rp[v.first][v.second+1];
if(!rp[v.first][v.second]){
pos.push({v.first-1, v.second});
pos.push({v.first, v.second-1});
}
}
}
}else{
cout << "1\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
