Submission #653115

#	Time	Username	Problem	Language	Result	Execution time	Memory
653115		pauloamed	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	536 ms	101976 KiB

tracks

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

const int MAXN = 4010;

int n, m; 
bool M[MAXN][MAXN];
bool on[MAXN][MAXN];

bool ok(int i, int j){
  if(i < 0 || j < 0 || i >= n || j >= m) return false;
  return on[i][j];
}

int DI[] = {0, 0, -1, 1};
int DJ[] = {-1, 1, 0, 0};

int32_t main(){
  cin.tie(NULL)->sync_with_stdio(false);
  cin >> n >> m;
  for(int i = 0; i < n; ++i){
    string s; cin >> s;
    for(int j = 0; j < m; ++j){
      if(s[j] == '.') on[i][j] = false;
      else{
        on[i][j] = true;
        M[i][j] = (s[j] == 'F');
      }
    }
  }

  int ans = 0;
  
  struct Node{
    int i, j, d;
  };

  deque<Node> q;
  q.push_front({0, 0, 1});
  on[0][0] = false;
  while(q.size()){
    auto [i, j, d] = q.front();
    q.pop_front();

    ans = max(ans, d);

    for(int k = 0; k < 4; ++k){
      int ni = i + DI[k];
      int nj = j + DJ[k];
      if(ok(ni, nj)){
        on[ni][nj] = false;
        if(M[ni][nj] != M[i][j]){
          q.push_back({ni, nj, d + 1});
        }else{
          q.push_front({ni, nj, d});
        }
      }
    }
  }

  cout << ans << "\n";

}

Compilation message (stderr)

tracks.cpp: In function 'int32_t main()':
tracks.cpp:42:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     auto [i, j, d] = q.front();
      |          ^

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