Submission #61396418

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* -------------------------------------- HEADER FILES ---------------------------------------- */
/**
 *    username:  aditya_0670
 *    created: 2025-01-04 01:53:22
 **/
  #include <bits/stdc++.h>
  using namespace std;
/* ------------------------------------ MACROS & CONSTANTS ------------------------------------ */
  #ifndef ONLINE_JUDGE
      #include "debug.h"
  #else
      #define debug(...) ;
  #endif
  #define int             long long
  #define all(v)          (v).begin(), (v).end()
  #define rall(v)         (v).rbegin(), (v).rend()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

/* -------------------------------------- HEADER FILES ---------------------------------------- */

/**
 *    username:  aditya_0670
 *    created: 2025-01-04 01:53:22
 **/

  #include <bits/stdc++.h>
  using namespace std;

/* ------------------------------------ MACROS & CONSTANTS ------------------------------------ */

  #ifndef ONLINE_JUDGE
      #include "debug.h"
  #else
      #define debug(...) ;
  #endif

  #define int             long long
  #define all(v)          (v).begin(), (v).end()
  #define rall(v)         (v).rbegin(), (v).rend()
  #define fastio          ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

  constexpr int MOD = 1E9 + 7;
  constexpr int INF = 1E18;

  vector<array<int,2>> horz_dir = {{0, 1}, {0, -1}};
  vector<array<int,2>> vert_dir = {{1, 0}, {-1, 0}};


/* ------------------------------------ OTHER FUNCTIONS ------------------------------------ */


/* ------------------------------------ LAMBDA TEMPLATE ------------------------------------- */

  auto solve = [] -> void
  {
      int n , m; cin >> n >> m;

      vector<string> g(n);
      for (auto& i : g) cin >> i;

      int s_i = -1, s_j = -1, e_i = -1, e_j = -1;

      for (int i = 0; i < n; i++)
          for (int j = 0; j < m; j++)
          {
             if (g[i][j] == 'S') s_i = i , s_j = j;
             if (g[i][j] == 'G') e_i = i , e_j = j;
          }

      auto bfs =[&](int s_i, int s_j, int e_i, int e_j) -> int
      {
           vector<vector<vector<int>>> d(n, vector<vector<int>>(m, vector<int>(2, INF)));

           queue<array<int,3>> q;

           d[s_i][s_j][0] = 0;
           d[s_i][s_j][1] = 0;

           q.push({s_i, s_j, 0});
           q.push({s_i, s_j, 1});

           while (!q.empty())
           {
               auto [c_i, c_j, ok] = q.front();
               q.pop();

               if (c_i == e_i && c_j == e_j) return d[c_i][c_j][ok];

               if (!ok)
               {
                   for (auto& [di, dj] : horz_dir)
                   {
                       int ni = c_i + di, nj = c_j + dj;

                       if (ni >= 0 && ni < n && nj >= 0 && nj < m && g[ni][nj]!= '#' && d[ni][nj][1] == INF)
                       {
                           d[ni][nj][1] = d[c_i][c_j][0] + 1;
                           q.push({ni, nj, 1});
                       }
                   }
               }
               else 
               {
                  for (auto& [di, dj] : vert_dir)
                  {
                      int ni = c_i + di, nj = c_j + dj;

                      if (ni >= 0 && ni < n && nj >= 0 && nj < m && g[ni][nj]!= '#' && d[ni][nj][0] == INF)
                      {
                          d[ni][nj][0] = d[c_i][c_j][1] + 1;
                          q.push({ni, nj, 0});
                      }
                  }
               }
           }

           return -1;
      };

      cout << bfs(s_i, s_j, e_i, e_j) << '\n';
  };

/* ------------------------------------ MAIN FUNCTION --------------------------------------- */

  signed main() 
  {
      fastio;

      int t = 1;
      while (t--) solve();

      return 0;
  }

Submission Info

Judge Result