Submission #1164617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164617		fryingduc	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	557 ms	151008 KiB

tracks

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int movex[] = {1, -1, 0, 0};
const int movey[] = {0, 0, 1, -1};
const int maxn = 4005;
int n, m; 
char a[maxn][maxn];
int d[maxn][maxn];

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> a[i][j];
    }
  }
  deque<tuple<int, int, int>> dq;
  dq.emplace_back(1, 1, 1);
  memset(d, 0x3f, sizeof(d));
  d[1][1] = 1;
  while (!dq.empty()) {
    auto [dist, x, y] = dq.front();
    dq.pop_front();
    if (dist > d[x][y]) continue;
    for (int move = 0; move < 4; ++move) {
      int r = x + movex[move], c = y + movey[move];
      if (r < 1 || c < 1 || r > n || c > m || a[r][c] == '.') continue;
      if (d[r][c] > d[x][y] + (a[r][c] != a[x][y])) {
        d[r][c] = d[x][y] + (a[r][c] != a[x][y]);
        if (a[r][c] == a[x][y]) {
          dq.emplace_front(d[r][c], r, c);
        } else {
          dq.emplace_back(d[r][c], r, c);
        }
      }
    }
  }
  int res = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (d[i][j] < 5e8) {
        res = max(res, d[i][j]);
      }
    }
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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