Submission #76764327

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int h,w;
vector<string> g;
vector<int> comp;
vector<vector<pair<int,ll>>> node;
int sx,sy,gx,gy;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

inline int id(int x,int y){
    return x*w+y;
}

inline void dfs(int x,int y,int c){
    if(x<0||x>=h||y<0||y>=w) return;
    if(g[x][y]!='V') return;
    int p=id(x,y);
    if(comp[p]!=-1) return;
    comp[p]=c;
    for(int d=0;d<4;++d) dfs(x+dx[d],y+dy[d],c);
}

signed main(){
    scanf("%d%d",&h,&w);
    g.resize(h);
    char tmp[200005];
    for(int i=0;i<h;++i){
        scanf("%s",tmp);
        g[i]=string(tmp);
        for(int j=0;j<w;++j){
            if(g[i][j]=='S') sx=i,sy=j;
            if(g[i][j]=='G') gx=i,gy=j;
        }
    }
    int N=h*w;
    comp.assign(N,-1);
    int cc=0;
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            if(g[i][j]=='V'&&comp[id(i,j)]==-1){
                dfs(i,j,cc);
                cc++;
            }
        }
    }
    node.resize(N+cc);
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            if(g[i][j]=='X') continue;
            int u=id(i,j);
            for(int d=0;d<4;++d){
                int ni=i+dx[d],nj=j+dy[d];
                if(ni<0||ni>=h||nj<0||nj>=w) continue;
                if(g[ni][nj]=='X') continue;
                int v=id(ni,nj);
                ll wg=1;
                if(g[ni][nj]=='V') wg=2;
                node[u].push_back({v,wg});
            }
            if(g[i][j]=='V'){
                int c=comp[u];
                node[u].push_back({N+c,0});
                node[N+c].push_back({u,0});
            }
        }
    }
    vector<ll> dist(N+cc,1e18);
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<>> pq;
    int start=id(sx,sy);
    dist[start]=0;
    pq.push({0,start});
    while(!pq.empty()){
        auto [d,u]=pq.top(); pq.pop();
        if(d!=dist[u]) continue;
        for(auto [v,w]:node[u]){
            if(dist[v]>d+w){
                dist[v]=d+w;
                pq.push({dist[v],v});
            }
        }
    }
    int goal=id(gx,gy);
    if(dist[goal]>=1e18) printf("NO\n");
    else printf("%lld\n",dist[goal]);
    return 0;
}

Submission Info

Judge Result