Submission #790086

#	Time	Username	Problem	Language	Result	Execution time	Memory
790086		tch1cherin	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	699 ms	135548 KiB

tracks

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  for (auto &v : S) {
    cin >> v;
  }
  int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
  vector<vector<int>> dist(H, vector<int>(W, INT_MAX));
  deque<pair<int, int>> q;
  q.push_back({0, 0});
  int ans = dist[0][0] = 1;
  while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop_front();
    for (int d = 0; d < 4; d++) {
      int i = x + dx[d], j = y + dy[d];
      if (i >= 0 && i < H && j >= 0 && j < W && S[i][j] != '.' && dist[i][j] == INT_MAX) {
        if (S[i][j] == S[x][y]) {
          q.push_front({i, j});
          dist[i][j] = dist[x][y];
        } else {
          q.push_back({i, j});
          ans = max(ans, dist[i][j] = dist[x][y] + 1);
        }
      }
    }
  }
  cout << ans << "\n";
}

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