제출 #1285471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285471		lucaskojima	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	662 ms	112016 KiB

tracks

#include "bits/stdc++.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};

int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0);

  int n, m; cin >> n >> m;
  vector<string> ma(n); for (auto &x : ma) cin >> x;

  vector d(n, vector<int>(m, INF));
  deque<pii> q;
  q.push_front({0, 0});
  d[0][0] = 1;

  auto val = [&](int i, int j) -> bool {
    return 0 <= i && i < n && 0 <= j && j < m && ma[i][j] != '.';
  };

  int ans = 1;
  while (!q.empty()) {
    auto [x, y] = q.front(); q.pop_front();
    ans = max(ans, d[x][y]);

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

      int w = (ma[x][y] != ma[nx][ny]);
      if (d[x][y] + w < d[nx][ny]) {
        d[nx][ny] = d[x][y] + w;
        if (w == 0)
          q.push_front({nx, ny});
        else
          q.push_back({nx, ny});
      }
    }
  }

  cout << ans << nl;
  return 0;
}

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