제출 #481412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
481412		erlkonig	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	562 ms	135120 KiB

tracks

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

#define ll long long
#define ld long double
#define ar array
#define fi first
#define se second
#define ii pair <int, int>
#define vt vector
#define pb push_back
#define sz(x) (int)(x).size()
#define reset(a, x) memset(a, x, sizeof(a))
#define u128 __uint128_t

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<=(b):i>=(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, (e)-1, 1)
#define F_OR2(i, e) F_OR(i, 0, (e)-1, 1)
#define F_OR3(i, b, e) F_OR(i, (b), (e), 1)
#define F_OR4(i, b, e, s) F_OR(i, (b), (e), (s))
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define fo(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define each(x, a) for (auto& x: a)
#define END cerr << "\n";

#define error(args...) { \
  string _s = #args; \
  replace(_s.begin(), _s.end(), ',', ' '); \
  stringstream _ss(_s); \
  istream_iterator <string> _it(_ss); \
  err(_it, args); \
}

void err(istream_iterator<string> it) {}

template<typename T, typename... Args> 
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << "=" << a << ", ";
  err(++it, args...);
}

template<class T> void read(T& x) {
  cin >> x;
}

template<class H, class... T> void read(H& h, T&... t) {
  read(h);
  read(t...);
}

template<class A> void write(A x) {
  cout << x;
}

template<class H, class... T> void write(const H& h, const T&... t) { 
  write(h);
  write(t...);
}

void print() {
  write("\n");
}

template<class H, class... T> void print(const H& h, const T&... t) { 
  write(h);
  if(sizeof...(t))
    write(' ');
  print(t...);
}

#define file ""
//#define int ll

const long long INF = 2e18;
const int inf = 0x3c3c3c3c, N = 4e3;
int h, w, d[N][N];
deque <ii> dq;
string grid[N];

inline bool ok(int x, int y) {
  return (min(x, y) >= 0 && x < h && y < w && grid[x][y] != '.');
}

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

void solve() {
  read(h, w);
  fo(h) read(grid[i]);
  reset(d, inf);
  d[0][0] = 1;
  dq.pb({0, 0});
  while (sz(dq)) {
    ii u = dq.front();
    dq.pop_front();
    fo(4) {
      int newx = u.fi+dx[i];
      int newy = u.se+dy[i];
      if (!ok(newx, newy)) continue;
      int cost = grid[u.fi][u.se] != grid[newx][newy];
      if (d[newx][newy] > d[u.fi][u.se]+cost) {
        d[newx][newy] = d[u.fi][u.se]+cost;
        if (cost) dq.pb({newx, newy});
        else dq.push_front({newx, newy});
      }
    }
  }
  int ans = 0;
  fo(x, h) fo(y, w) if (ok(x, y)) ans = max(ans, d[x][y]);
  write(ans);
}

int32_t main() {
  //freopen(file".out", "w", stdout); freopen(file".in", "r", stdin);
  cin.tie(0)->sync_with_stdio(0);
  int Case = 1;
  //read(Case);
  fo(ttest, 1, Case) {
    //write("Case ", ttest, ": ");
    solve();
  }
}

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