Submission #1352228

#TimeUsernameProblemLanguageResultExecution timeMemory
1352228cpismayilmmdv985Tracks in the Snow (BOI13_tracks)C++20
19.79 / 100
611 ms137944 KiB
#ifdef LOCAL
#include ".debug.hpp"
#else
#define debug(...) 42
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

signed main() {
#ifndef VOID
   cin.tie(nullptr)->sync_with_stdio(false);
#endif

   int N, M;   cin >> N >> M;
   vector<vector<char>> A(N, vector<char> (M)); 
   for (int i = 0; i < N; i++)   for (int j = 0; j < M; j++)   cin >> A[i][j];
   int ans = 1;
   vector<vector<bool>> vis(N, vector<bool> (M));
   auto free = [&](const int &x, const int &y) -> bool {
      return x >= 0 && y >= 0 && x < N && y < M && !vis[x][y];
   };
   const vector<int> DX = {1, -1, 0, 0}, DY = {0, 0, 1, -1};
   char turn = A[0][0]; 
   deque<array<int, 2>> dq;   dq.push_back({0, 0});
   if (turn == '.') {
      cout << "0\n";
      return 0;
   }
   while (!dq.empty()) {
      int X, Y;
      if (turn == 'R')  X = dq.front()[0], Y = dq.front()[1], dq.pop_front();
      else              X = dq.back()[0], Y = dq.back()[1], dq.pop_back();
      if (turn == 'R' && A[X][Y] == 'F')  turn = 'F', ans++;
      else if (turn == 'F' && A[X][Y] == 'R')  turn = 'R', ans++;
      vis[X][Y] = true;
      for (int d = 0; d < 4; d++) {
         int toX = X + DX[d], toY = Y + DY[d];
         if (!free(toX, toY)) continue;
         if (A[toX][toY] == 'F') dq.push_back({toX, toY});
         else                    dq.push_front({toX, toY});
      }
   }
   cout << ans;

   return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...