Submission #1124677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124677		aykhn	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	984 ms	208604 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F

int A[4] = {0, 0, -1, 1};
int B[4] = {-1, 1, 0, 0};

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  char a[n][m];
  int d[n][m];
  for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> a[i][j], d[i][j] = inf;
  d[0][0] = 1;
  assert(a[0][0] == a[n - 1][m - 1]);
  deque<array<int, 2>> q;
  q.push_back({0, 0});
  int res = 0;
  while (!q.empty())
  {
    array<int, 2> x = q.front();
    q.pop_front();
    for (int k = 0; k < 4; k++)
    {
      int X = x[0] + A[k], Y = x[1] + B[k];
      if (min(X, Y) < 0 || X >= n || Y >= m || a[X][Y] == '.') continue;
      if (a[X][Y] == a[x[0]][x[1]] && d[X][Y] > d[x[0]][x[1]])
      {
        d[X][Y] = d[x[0]][x[1]];
        q.push_front({X, Y});
      } 
      else if (a[X][Y] != a[x[0]][x[1]] && d[X][Y] > d[x[0]][x[1]] + 1)
      {
        d[X][Y] = d[x[0]][x[1]] + 1;
        q.push_back({X, Y});
      }
    }
    res = max(res, d[x[0]][x[1]]);
  }
  cout << res << '\n';
}

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