Submission #1092784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092784		juicy	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	780 ms	174404 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vector a(n, vector<char>(m));
  for (int i = 0; i < n; ++i) {
    for (auto &c : a[i]) {
      cin >> c;
    }
  }
  vector d(n, vector<int>(m, 1e9));
  vector vis(n, vector<bool>(m));
  auto inside = [&](int r, int c) {
    return 0 <= r && r < n && 0 <= c && c < m && a[r][c] != '.' && !vis[r][c];
  }; 
  deque<array<int, 2>> dq{{0, 0}};
  d[0][0] = 1;
  int res = 0;
  while (dq.size()) {
    auto [r, c] = dq.front(); dq.pop_front();
    if (vis[r][c]) {
      continue;
    }
    res = d[r][c];
    vis[r][c] = 1;
    for (int k = 0; k < 4; ++k) {
      int i = r + dx[k], j = c + dy[k];
      if (inside(i, j)) {
        if (a[r][c] == a[i][j]) {
          d[i][j] = min(d[i][j], d[r][c]);
          dq.push_front({i, j});
        } else {
          d[i][j] = min(d[i][j], d[r][c] + 1);
          dq.push_back({i, j});
        }
      }
    }
  }
  cout << res;
  return 0;
}

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