Submission #61398146

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#pragma GCC optimize("O3,unroll-loops")
#include "bits/stdc++.h"
#ifdef AlRntn
#include "debug.hpp"
#else
#define debug(...) void(0)
#define tstr(...) void(0)
#endif
using int64 = int64_t;
using uint64 = uint64_t;
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
#define fi first
#define se second
#define sz(x) int64_t(x.size())
#define all(x) x.begin(), x.end()
#define spc ' '
#define endl '\n'
#define pb push_back
#define mp make_pair
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#pragma GCC optimize("O3,unroll-loops")
#include "bits/stdc++.h"
#ifdef AlRntn
#include "debug.hpp"
#else
#define debug(...) void(0)
#define tstr(...) void(0)
#endif
using int64 = int64_t;
using uint64 = uint64_t;
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
#define fi first
#define se second
#define sz(x) int64_t(x.size())
#define all(x) x.begin(), x.end()
#define spc ' '
#define endl '\n'
#define pb push_back
#define mp make_pair
#define ever ;1;
constexpr int64_t inf = 5e18 + 100;
constexpr int64_t mod1 = 1e9+7;
constexpr int64_t mod2 = 998244353;
constexpr int64_t mod3 = 1e9+9;
constexpr int64_t mod4 = (1ll<<31) - 1;
constexpr long double PI = 2*asinl(1.0);
int dx[4] = {0 , 1 , 0 , -1}; // clockwise from north
int dy[4] = {-1 , 0 , 1 , 0};
int dx2[8] = {0 , 1 , 1 , 1 , 0 , -1 , -1 , -1}; // clockwise from north
int dy2[8] = {-1 , -1 , 0 , 1 , 1 , 1 , 0 , -1};
const int N = 1e6 + 50, L = 25, M = 1000 + 50;
int64_t H, W;
std::vector<std::string> G;
int64_t dis[2][M][M];
bool inside(int64_t i, int64_t j){
    return i >= 0 && i < H && j >= 0 && j < W;
}
void dfs(bool type, int64_t si, int64_t sj, bool ver){
    std::stack<std::pair<std::pair<int64_t, int64_t>, bool>> DFS;
    DFS.push(std::make_pair(std::make_pair(si, sj), ver));
    while(!DFS.empty()){
        int64_t i = DFS.top().fi.fi;
        int64_t j = DFS.top().fi.se;
        bool ver = DFS.top().se;
        DFS.pop();
        for(int64_t x = ver; x < 4; x += 2){
            if(inside(i + dx[x], j + dy[x]) && (dis[type][i + dx[x]][j + dy[x]] == 0 || dis[type][i + dx[x]][j + dy[x]] > dis[type][i][j] + 1) && G[i + dx[x]][j + dy[x]] != '#'){
                dis[type][i + dx[x]][j + dy[x]] = dis[type][i][j] + 1;
                DFS.push(std::make_pair(std::make_pair(i + dx[x], j + dy[x]), !ver));
            }
        }
    }
}
int32_t main(){
#ifdef AlRntn
freopen("inputf.in" , "r" , stdin); freopen("outputf.out" , "w" , stdout); freopen("errorf.out" , "w" , stderr);
#endif
    using namespace std;
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int32_t tc=1;
//#define TestCases
#ifdef TestCases
    std::cin >> tc;
#endif
    while(tc--){
        cin>>H>>W;G.resize(H);
        for(auto &ss : G) cin >> ss;
        int64_t st_i = 0, st_j = 0;
        int64_t en_i = 0, en_j = 0;
        for(int64_t i = 0; i < H; i++){
            for(int64_t j = 0; j < W; j++){
                if(G[i][j] == 'S') st_i = i, st_j = j;
                if(G[i][j] == 'G') en_i = i, en_j = j;
            }
        }
        dis[0][st_i][st_j] = dis[1][st_i][st_j] = 1;
        dfs(0, st_i, st_j, 0);
        dfs(1, st_i, st_j, 1);
        if(dis[0][en_i][en_j] || dis[1][en_i][en_j]){
            if(dis[0][en_i][en_j] == 0) cout << dis[1][en_i][en_j] - 1 << endl;
            else if(dis[1][en_i][en_j] == 0) cout << dis[0][en_i][en_j] - 1 << endl;
            else cout << (std::min(dis[1][en_i][en_j], dis[0][en_i][en_j]) - 1) << endl;
        }else{
            cout << "-1\n";
        }
    }
    return 0;
}

Submission Info

Judge Result