이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
vector<vector<char> > g;
int h, w;
using ii = pair<int, int>;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>h>>w;
g = vector<vector<char> >(h, vector<char>(w));
for(int i = 0; i < h; i++){
string inp; cin>>inp;
for(int j = 0; j < w; j++){
if(inp[j] == '.'){
g[i][j] = 2;
}else if(inp[j] == 'F'){
g[i][j] = 0;
}else if(inp[j] == 'R'){
g[i][j] = 1;
}
}
}
if(g[0][0] == 2){
cout<<0<<endl;
return 0;
}
if(g[0][0] != 0){ //flip if first one is 1
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
if(g[i][j] != 2) g[i][j] = 1 - g[i][j];
}
}
}
//top left cell is now 0
vector<ii> active;
active.push_back({0, 0});
int ans = 0;
g[0][0] = 3;
vector<ii> del = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while(!active.empty()){
//cout<<"ANS "<<ans<<endl;
vector<ii> nact;
while(!active.empty()){
int x = active.back().first, y = active.back().second;
//cout<<"CUR "<<x<<" "<<y<<endl;
active.pop_back();
for(ii vec: del){
int xd = x + vec.first, yd = y + vec.second;
if(xd < 0 || xd >= h || yd < 0 || yd >= w) continue;
//cout<<"CHECKING "<<xd<<" "<<yd<<" "<<(int)g[xd][yd]<<endl;
if(g[xd][yd] == 3){ // means its visited
}else if(g[xd][yd] == 2){ //empty
}else if(g[xd][yd] == (ans%2)){
active.push_back({xd, yd});
//cout<<"PUSHED "<<xd<<" "<<yd<<endl;
g[xd][yd] = 3;
}else{
nact.push_back({xd, yd});
//cout<<"PUSHED D"<<xd<<" "<<yd<<endl;
g[xd][yd] = 3;
}
}
}
// for(ii cur: nact){
// cout<<"NACT "<<cur.first<<" "<<cur.second<<endl;
// }
ans++;
active = nact;
nact.clear();
}
cout<<ans<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |