Submission #1305728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305728		wavebreaker	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	356 ms	38668 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "/Users/mohammadrehan/Documents/code/algo/debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define endl "\n"

const int MOD = 998244353;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<string> ve(n);
  for (int i = 0; i < n; i++) {
    cin >> ve[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if(ve[i][j] == 'R') {
        ve[i][j] = '0';
      } else if(ve[i][j] == 'F'){
        ve[i][j] = '1';
      }
    }
  }

  vector<queue<array<int, 2>>> que(2);
  bool who = ve[n - 1][m - 1] - '0';
  que[who].push({n - 1, m - 1});
  int cnt = 0;
  while(!que[0].empty() || !que[1].empty()) {
    while(!que[who].empty()) {
      auto [x, y] = que[who].front();
      que[who].pop();
      if(x != 0) { // TOP
        if(ve[x - 1][y] != '.') {
          que[ve[x - 1][y] - '0'].push({x - 1, y});
          ve[x - 1][y] = '.';
        }
      }
      if(y != m - 1) { // RIGHT
        if(ve[x][y + 1] != '.') {
          que[ve[x][y + 1] - '0'].push({x, y + 1});
          ve[x][y + 1] = '.';
        }
      }
      if(x != n - 1) { // BOT
        if(ve[x + 1][y] != '.') {
          que[ve[x + 1][y] - '0'].push({x + 1, y});
          ve[x + 1][y] = '.';
        }
      }
      if(y != 0) { // LEFT
        if(ve[x][y - 1] != '.') {
          que[ve[x][y - 1] - '0'].push({x, y - 1});
          ve[x][y - 1] = '.';
        }
      }
    }
    cnt++;
    who = !who;
  }
  cout << cnt;
}

void init() {}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  init();
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
    cout << endl;
    cout.flush();
  }
  return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70