제출 #1251653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251653		kunzaZa183	Tracks in the Snow (BOI13_tracks)	C++20	84.69 / 100	2099 ms	105756 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  vector<string> vs(n);
  for (auto &a : vs)
    cin >> a;

  vector<vector<int>> vvi(n, vector<int>(m, -1));
  priority_queue<array<int, 3>> pqai3;
  pqai3.push({-1, 0, 0});

  const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
  while (!pqai3.empty()) {
    auto [w, x, y] = pqai3.top();
    pqai3.pop();
    w = -w;

    if (vvi[x][y] != -1) {
      continue;
    }

    vvi[x][y] = w;
    // cout << x << " " << y << " " << w << "\n";

    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i], ny = y + dy[i];

      if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
        if (vvi[nx][ny] == -1 && vs[nx][ny] != '.') {
          if (vs[nx][ny] == vs[x][y])
            pqai3.push({-w, nx, ny});
          else
            pqai3.push({-w - 1, nx, ny});
        }
      }
    }
  }

  int maxi = 0;
  for (auto &a : vvi)
    for (auto b : a)
      maxi = max(maxi, b);
  cout << maxi << "\n";
}

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