Submission #1150525

---

Source Code Expand

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#include<map>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
int mx[]={1,-1,0,0};
int my[]={0,0,1,-1};
int main(){
    queue<pii>que; pii s,c,g,now;
    int h,w; cin>>h>>w;
    vector<vector<char>>v(h,vector<char>(w));
    rep(i,h)rep(j,w){
        cin>>v[i][j];
        if(v[i][j]=='S')s=pii(i,j);
        if(v[i][j]=='C')c=pii(i,j);
        if(v[i][j]=='G')g=pii(i,j);
        }
    vvi d1(h,vi(w,INF)),d2(h,vi(w,INF));
    d1[s.first][s.second]=0;
    que.push(s);
    bool flag=false;
    while(!que.empty()){
        now=que.front(); que.pop();
        if(now==c){break;flag=true;}
        rep(i,4){
            pii temp=pii(now.first+my[i],now.second+mx[i]);
            if(d1[temp.first][temp.second]==INF&&v[temp.first][temp.second]!='#'){
                que.push(temp);d1[temp.first][temp.second]=d1[now.first][now.second]+1;}
        }
    }
    ll ans=(ll)d1[c.first][c.second];
    while(!que.empty())que.pop();
    que.push(c);
    d2[c.first][c.second]=0;
    while(!que.empty()){
        now=que.front(); que.pop();
        if(now==g){break;flag=true;}
        rep(i,4){
            pii temp=pii(now.first+mx[i],now.second+my[i]);
            if(d2[temp.first][temp.second]==INF&&v[temp.first][temp.second]!='#'){
                que.push(temp);d2[temp.first][temp.second]=d2[now.first][now.second]+1;}
        }
    }
    if(!flag)return puts("-1")*0;
    cout<<ans+d2[g.first][g.second]<<endl;
}

Submission Info

Judge Result