Submission #942374

#	Time	Username	Problem	Language	Result	Execution time	Memory
942374		myst6	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	516 ms	111964 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int di[4] = {1, -1, 0, 0};
int dj[4] = {0, 0, 1, -1};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int H, W;
  cin >> H >> W;
  vector<string> grid(H);
  for (int i=0; i<H; i++) cin >> grid[i];
  vector<vector<int>> dist(H, vector<int>(W, -1));
  deque<pair<int,int>> Q;
  dist[H-1][W-1] = 1;
  Q.push_back({H-1, W-1});
  while (Q.size()) {
    auto [i, j] = Q.front(); Q.pop_front();
    for (int k=0; k<4; k++) {
      int i2 = i + di[k];
      int j2 = j + dj[k];
      if (i2 < 0 || j2 < 0 || i2 >= H || j2 >= W) continue;
      if (grid[i2][j2] == '.') continue;
      int d = dist[i][j] + (grid[i][j] != grid[i2][j2]);
      if (dist[i2][j2] == -1 || d < dist[i2][j2]) {
        dist[i2][j2] = d;
        if (grid[i][j] == grid[i2][j2]) Q.push_front({i2, j2});
        else Q.push_back({i2, j2});
      }
    }
  }
  int ans = 0;
  for (int i=0; i<H; i++) {
    for (int j=0; j<W; j++) {
      ans = max(ans, dist[i][j]);
    }
  }
  cout << ans << "\n";
  return 0;
}

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