Codeforces Round #355 D. Vanya and Treasure

問題

Problem - D - Codeforces

解法

Codeforces Round #355 (Div. 2) Editorial - Codeforces

ダイクストラと全列挙を使い分ける。

コード

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

typedef pair<int, int> P;
typedef tuple<int, int, int> E;

template <class T, class U>
void chmin(T &t, U f) {
  if (t > f) t = f;
}

int dist(pair<int, int> a, pair<int, int> b) {
  return abs(a.first - b.first) + abs(a.second - b.second);
}

const int DX[] = {0, 0, 1, -1};
const int DY[] = {1, -1, 0, 0};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int64_t N, M, H;
  cin >> N >> M >> H;

  vector<vector<int>> maze(N, vector<int>(M));
  vector<vector<P>> g(H + 1);
  g[0].emplace_back(0, 0);
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < M; ++j) {
      cin >> maze[i][j];
      g[maze[i][j]].emplace_back(i, j);
    }

  vector<vector<int>> dists(N, vector<int>(M, 1e9));
  for (const auto &p : g[1]) dists[p.first][p.second] = dist(g[0][0], p);
  for (int h = 1; h < H; ++h) {
    if (g[h].size() * g[h + 1].size() > 10000000) {
      priority_queue<E, vector<E>, greater<E>> que;
      vector<vector<int>> tmpdist(N, vector<int>(M, 1e9));
      for (const auto &p : g[h]) {
        que.emplace(dists[p.first][p.second], p.first, p.second);
        tmpdist[p.first][p.second] = dists[p.first][p.second];
      }
      while (!que.empty()) {
        int d, i, j;
        tie(d, i, j) = que.top();
        que.pop();
        for (int k = 0; k < 4; ++k) {
          int ni = i + DX[k];
          int nj = j + DY[k];
          if (ni < 0 || ni >= N) continue;
          if (nj < 0 || nj >= M) continue;
          if (tmpdist[ni][nj] < 1e9) continue;

          tmpdist[ni][nj] = tmpdist[i][j] + 1;
          que.emplace(tmpdist[ni][nj], ni, nj);
        }
      }
      for (const auto &p : g[h + 1])
        dists[p.first][p.second] = tmpdist[p.first][p.second];
    } else {
      for (const auto &from : g[h])
        for (const auto &to : g[h + 1]) {
          chmin(dists[to.first][to.second],
                dists[from.first][from.second] + dist(from, to));
        }
    }
  }

  int ans = 1e9;
  for (const auto &last : g[H]) chmin(ans, dists[last.first][last.second]);
  cout << ans << endl;
}