提出 #11773947

---

ソースコード 拡げる

#include <vector>
#include <queue>
using i64 = long long;

/*
 * delta(V v, fn (V t, i64 weight))
 * index(V v) -> int
 */
template<class V, class W, class Delta, class Index>
std::vector<i64> dial01(std::size_t N, W inf, V s, Delta delta, Index index) {
  std::vector<i64> dist(N, inf);
  using P = std::pair<V, W>;
  std::deque<P> que;
  dist[index(s)] = 0;
  que.push_back({ s, dist[index(s)]});
  while(!que.empty()) {
    V v = que.front().first;
    W d = que.front().second;
    que.pop_front();
    if(dist[index(v)] < d) continue;
    delta(v, [&](V t, i64 weight) {
        if(dist[index(t)] > dist[index(v)] + weight) {
          dist[index(t)] = dist[index(v)] + weight;
          if(weight == 0) que.push_front({ t, dist[index(t)] });
          else que.push_back({ t, dist[index(t)] });
        }
    });
  }
  return dist;
}

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class F>
struct lattice_delta {
  i64 H, W;
  F f;
  using P = std::pair<i64, i64>;
  lattice_delta(i64 H, i64 W, F f): H(H), W(W), f(f) {}
  template<class Func>
  void operator()(P v, Func func) {
    const static vector<i64> dx { 1, 0, -1, 0 };
    i64 i = v.first;
    i64 j = v.second;
    for(i64 q = 0; q < 2; q++) {
      i64 x = i + dx[q];
      i64 y = j + dx[q ^ 1];
      if(0 <= x && x < H && 0 <= y && y < W) {
        f(P(i, j), P(x, y), func);
      }
    }
  }
};

template<class F>
lattice_delta<F> make_lattice_delta(i64 H, i64 W, F f) { return lattice_delta<F>(H, W, f); }

struct lattice_index {
  i64 H, W;
  using P = std::pair<i64, i64>;
  lattice_index(i64 H, i64 W): H(H), W(W) {}
  i64 operator()(P v) {
    return v.first * W + v.second;
  }
};


int main() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  i64 H, W;
  cin >> H >> W;
  vector<string> S(H);
  rep(i,0,H) {
    cin >> S[i];
  }
  using P = std::pair<i64, i64>;
  vector<i64> dx { 1, 0, -1, 0 };
  auto delta = make_lattice_delta(H, W,
      [&](P v, P t, auto func) {
        if(S[v.first][v.second] != S[t.first][t.second] && S[t.first][t.second] == '#') func(t, 1);
        else func(t, 0);
        }
      );
  auto index = lattice_index(H, W);
  auto res = dial01(H * W, (i64)(1e9), P(0, 0), delta, index);
  auto ans = res[index({ H - 1, W - 1 })];
  if(S[0][0] == '#') {
    ans++;
  }
  cout << ans << endl;
}

提出情報

ジャッジ結果