結果

問題 No.124 門松列(3)
ユーザー ninoinuininoinui
提出日時 2020-11-23 07:23:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 83 ms / 5,000 ms
コード長 2,502 bytes
コンパイル時間 3,653 ms
コンパイル使用メモリ 218,464 KB
実行使用メモリ 18,400 KB
最終ジャッジ日時 2023-09-30 23:38:20
合計ジャッジ時間 4,892 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
10,340 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 55 ms
14,828 KB
testcase_04 AC 82 ms
17,728 KB
testcase_05 AC 82 ms
18,400 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 3 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 7 ms
4,380 KB
testcase_17 AC 3 ms
4,380 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 3 ms
4,376 KB
testcase_20 AC 5 ms
4,376 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 4 ms
4,376 KB
testcase_23 AC 29 ms
8,224 KB
testcase_24 AC 43 ms
10,964 KB
testcase_25 AC 43 ms
11,012 KB
testcase_26 AC 15 ms
5,820 KB
testcase_27 AC 10 ms
4,712 KB
testcase_28 AC 82 ms
17,716 KB
testcase_29 AC 83 ms
17,764 KB
権限があれば一括ダウンロードができます

ソースコード

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