이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIM 1010
using namespace std;
int a[DIM][DIM],viz[DIM][DIM];
deque <pair<int,int> > c,w;
int n,m,i,j,q,x,y;
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>m;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
cin>>a[i][j];
for (i=0;i<=m+1;i++)
a[0][i] = a[n+1][i] = 1;
for (i=1;i<=n;i++)
a[i][0] = a[i][m+1] = 1;
c.push_back(make_pair(1,1));
viz[1][1] = 1;
while (!c.empty()){
int i = c.front().first;
int j = c.front().second;
c.pop_front();
if (!a[i][j+1] && !viz[i][j+1]){
c.push_back(make_pair(i,j+1));
viz[i][j+1] = 1;
}
if (!a[i+1][j] && !viz[i+1][j]){
c.push_back(make_pair(i+1,j));
viz[i+1][j] = 1;
}
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (!viz[i][j] && !a[i][j])
a[i][j] = 1;
cin>>q;
for (;q--;){
cin>>x>>y;
c.clear(), w.clear();
c.push_back(make_pair(x,y));
w.push_back(make_pair(x,y));
a[x][y] = 1;
int ok = 1;
while (!c.empty()){
int i = c.front().first;
int j = c.front().second;
c.pop_front();
if (i == n && j == m){
ok = 0;
break;
}
if (!a[i][j+1] && a[i-1][j+1]){
c.push_back(make_pair(i,j+1));
w.push_back(make_pair(i,j+1));
a[i][j+1] = 1;
}
if (!a[i+1][j] && a[i+1][j-1]){
c.push_back(make_pair(i+1,j));
w.push_back(make_pair(i+1,j));
a[i+1][j] = 1;
}
}
cout<<ok<<"\n";
if (!ok){
/// trb sa demarchez
for (auto it : w)
a[it.first][it.second] = 0;
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |