結果

問題 No.124 門松列(3)
ユーザー ninoinui
提出日時 2020-11-23 07:23:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 94 ms / 5,000 ms
コード長 2,502 bytes
コンパイル時間 2,677 ms
コンパイル使用メモリ 212,976 KB
最終ジャッジ日時 2025-01-16 04:50:32
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template <typename T, typename U> bool cmin(T &a, U b) { return a > b && (a = b, true); }
template <typename T, typename U> bool cmax(T &a, U b) { return a < b && (a = b, true); }

template <typename T> class Dijkstra {
private:
  struct edge {
    int to;
    T cost;
  };
  vector<vector<edge>> G;
  vector<T> D;

public:
  Dijkstra(int n) : G(n), D(n, numeric_limits<T>::max()) {}
  void add(int from, int to, T cost) { G.at(from).push_back((edge){to, cost}); }
  vector<T> solve(int start) {
    using pti = pair<T, int>;
    priority_queue<pti, vector<pti>, greater<pti>> Q;
    D.at(start) = 0;
    Q.push(pti(0, start));
    while (Q.size()) {
      auto [dist, now] = Q.top();
      Q.pop();
      if (D.at(now) < dist) continue;
      for (auto [next, cost] : G.at(now)) {
        if (D.at(next) > D.at(now) + cost) {
          D.at(next) = D.at(now) + cost;
          Q.push(pti(D.at(next), next));
        }
      }
    }
    return D;
  }
  void reset() { fill(D.begin(), D.end(), numeric_limits<T>::max()); }
};

signed main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  int W, H;
  cin >> W >> H;
  vector<vector<char>> S(H, vector<char>(W));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> S.at(i).at(j);
    }
  }

  Dijkstra<long> D(H * W * 10);
  auto id = [&](int h, int w) { return W * h + w; };
  auto iskd = [&](int a, int b, int c) {
    if (a == b || b == c || c == a) return false;
    if (b == max({a, b, c})) return true;
    if (b == min({a, b, c})) return true;
    return false;
  };

  vector<int> mh{-1, 0, 1, 0};
  vector<int> mw{0, 1, 0, -1};

  for (int h = 0; h < H; h++) {
    for (int w = 0; w < W; w++) {
      for (int i = 0; i < 4; i++) {
        int nh = h + mh.at(i);
        int nw = w + mw.at(i);
        if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
        for (int a = 1; a <= 9; a++) {
          int b = S.at(h).at(w) - '0';
          int c = S.at(nh).at(nw) - '0';
          if (iskd(a, b, c))
            D.add(H * W * a + id(h, w), H * W * b + id(nh, nw), 1);
          else if (!h && !w)
            D.add(H * W * a + id(h, w), H * W * b + id(nh, nw), 1);
        }
      }
    }
  }

  int ans = INT_MAX;
  for (int i = 1; i <= 9; i++) {
    auto tmp = D;
    auto V = tmp.solve(H * W * i);
    for (int j = 1; j <= 9; j++) {
      cmin(ans, V.at(H * W * j + id(H - 1, W - 1)));
    }
  }
  if (ans == INT_MAX) ans = -1;
  cout << ans << "\n";
}
0