Submission #76393076

---

Source Code Expand

//#define _GLIBCXX_DEBUG
//提出の際、1行目はコメントアウトすること
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
#define rep(a,b) for(ll a=0;a<b;a++)
#define rrep(a,b) for(ll a=b-1;a>=0;a--)
const long double pai=3.14159265358979323;
using Pair = pair<ll,ll>;
#define MOD 998244353
#define INF 1000000000000000000
#define MINF -1000000000000000000
using vll = vector<ll>;
using vvll = vector<vll>;
#include <atcoder/all>
using namespace atcoder;

const ll dx[]={1,-1,0,0};
const ll dy[]={0,0,1,-1};

bool IN(ll x,ll y,ll H,ll W){
    if(0<=x && x<H && 0<=y && y<W){return 1;}
    else{return 0;}
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N;
    cin>>N;
    vector<vector<char>> S(N,vector<char>(N));
    Pair st,gl;
    rep(i,N){
        rep(j,N){
            cin>>S[i][j];
            if(S[i][j]=='S'){st={i,j};}
            if(S[i][j]=='G'){gl={i,j};}
        }
    }

    vvll dist(N,vll(N,INF));
    queue<Pair> que;
    que.push(st);
    dist[st.first][st.second]=1;
    while(!que.empty()){
        auto [x,y]=que.front();
        que.pop();
        rep(k,4){
            ll rx=x+dx[k];
            ll ry=y+dy[k];
            if(IN(rx,ry,N,N) && S[rx][ry]!='#' && dist[rx][ry]==INF){
                dist[rx][ry]=dist[x][y]+1;
                que.push({rx,ry});
            }
        }

    }

    cout<<dist[gl.first][gl.second]<<endl;


}

Submission Info

Judge Result