이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define vi vector<int>
#define iii tuple<int,int,int>
typedef vector<ii> vii;
int R,C,Sx,Sy,Cx,Cy;
char G[1005][1005];
vi AL[1005][1005];
vii AL2[300000];
ii Start[300000];
ii End[300000];
int32_t main(){
cin>>R>>C;
for (int i=0; i<R; i++){
for (int j=0; j<C; j++){
cin>>G[i][j];
if (G[i][j]=='S'){
Sx = i; Sy = j;
}if (G[i][j]=='C'){
Cx = i; Cy = j;
}
}
}
int cnt=0, num=0;
for (int i=0; i<R; i++){
for (int j=0; j<C; j++){
if (G[i][j]=='#'){
if (num>0) End[cnt]=ii({i,j-1});
cnt++;
num=0;
}else{
if (num==0) Start[cnt]=ii({i,j});
AL2[cnt].emplace_back(i,j);
AL[i][j].emplace_back(cnt);
num++;
}
}
if (num>0) End[cnt]=ii({i,C-1});
cnt++;
num=0;
}
Start[cnt] = make_pair(0,0);
for (int j=0; j<C; j++){
for (int i=0; i<R; i++){
if (G[i][j]=='#'){
if (num>0) End[cnt]=make_pair(i-1,j);
cnt++;
num=0;
}else{
if (num==0) Start[cnt]=make_pair(i,j);
AL2[cnt].emplace_back(i,j);
AL[i][j].emplace_back(cnt);
num++;
}
}
if (num>0) End[cnt]=make_pair(R-1,j);
cnt++;
num=0;
}
queue<ii> BFS;
map<ii,ii> prev;
prev[ii(Sx, Sy)] = make_pair(-1,-1);
BFS.push(make_pair(Sx,Sy));
while (!BFS.empty()){
ii curr = BFS.front(); BFS.pop();
ii adj;
if (curr.second!=-1){
for (auto nb : AL[curr.first][curr.second]){
pair<int,int> p_ = make_pair(nb, -1);
if (prev.find(p_)==prev.end()){
prev[p_]=curr;
BFS.push(p_);
}
}
}else{
for (auto nb : AL2[curr.first]){
if (prev.find(nb)==prev.end()){
prev[nb]=curr;
BFS.push(nb);
}
}
}
}
ii curr = make_pair(Cx,Cy);
int curr_extra;
int ans=0;
while (curr != ii({-1,-1})){
ii parent = prev.find(curr)->second;
if (parent.second == -1){
curr_extra = parent.first;
continue;
}
ii S_=Start[curr_extra], E_=End[curr_extra];
if (curr.first == parent.first){
// x is the same
int top = min(curr.second, parent.second);
int bot = max(curr.second, parent.second);
ans += min(bot-top, E_.second - bot + top - S_.second + 1);
}else if (curr.second == parent.second){
// y is the same
int top = min(curr.first, parent.first);
int bot = max(curr.first, parent.first);
ans += min(bot-top, E_.first - bot + top - S_.first + 1);
}
curr = parent;
}
cout<<ans;
}
컴파일 시 표준 에러 (stderr) 메시지
portals.cpp: In function 'int32_t main()':
portals.cpp:99:28: warning: 'curr_extra' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | ii S_=Start[curr_extra], E_=End[curr_extra];
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |