fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct RadixHeap {
  5.     using U = unsigned int;
  6.     vector<pair<U,int>> b[33];
  7.     U last = 0;
  8.     bool empty() const { for (int i = 0; i < 33; ++i) if (!b[i].empty()) return false; return true; }
  9.     void push(U key, int val) {
  10.         int idx = (key == last) ? 0 : 32 - __builtin_clz(key ^ last);
  11.         b[idx].push_back({key, val});
  12.     }
  13.     pair<U,int> pop() {
  14.         if (b[0].empty()) {
  15.             int i = 1; while (b[i].empty()) ++i;
  16.             U nl = UINT_MAX;
  17.             for (auto &p : b[i]) if (p.first < nl) nl = p.first;
  18.             for (auto &p : b[i]) {
  19.                 int idx = (p.first == nl) ? 0 : 32 - __builtin_clz(p.first ^ nl);
  20.                 b[idx].push_back(p);
  21.             }
  22.             b[i].clear();
  23.             last = nl;
  24.         }
  25.         auto res = b[0].back(); b[0].pop_back(); return res;
  26.     }
  27. };
  28.  
  29. int main() {
  30.     ios::sync_with_stdio(false);
  31.     cin.tie(nullptr);
  32.     int n, m; 
  33.     if (!(cin >> n >> m)) return 0;
  34.     vector<string> g(n);
  35.     for (int i = 0; i < n; ++i) cin >> g[i];
  36.     int N = n * m;
  37.     vector<int> a(N);
  38.     for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) a[i*m + j] = g[i][j] - '0';
  39.  
  40.     vector<int> border[4];
  41.     for (int j = 0; j < m; ++j) border[0].push_back(j);
  42.     for (int j = 0; j < m; ++j) border[1].push_back((n-1)*m + j);
  43.     for (int i = 0; i < n; ++i) border[2].push_back(i*m);
  44.     for (int i = 0; i < n; ++i) border[3].push_back(i*m + (m-1));
  45.  
  46.     vector<array<int,4>> nei(N);
  47.     for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
  48.         int id = i*m + j;
  49.         nei[id][0] = (i ? id - m : -1);
  50.         nei[id][1] = (i + 1 < n ? id + m : -1);
  51.         nei[id][2] = (j ? id - 1 : -1);
  52.         nei[id][3] = (j + 1 < m ? id + 1 : -1);
  53.     }
  54.  
  55.     const int INF = 0x3f3f3f3f;
  56.     long long ans = INF;
  57.     const int S = 16;
  58.  
  59.     vector<int> w(N);
  60.     vector<int> dist(S * N);
  61.     vector<uint16_t> have(N);
  62.  
  63.     for (int c = 0; c <= 9; ++c) {
  64.         for (int i = 0; i < N; ++i) w[i] = abs(a[i] - c);
  65.         fill(dist.begin(), dist.end(), INF);
  66.         fill(have.begin(), have.end(), 0);
  67.  
  68.         RadixHeap pq;
  69.         for (int b = 0; b < 4; ++b) {
  70.             int mk = 1 << b;
  71.             int base = mk * N;
  72.             for (int v : border[b]) {
  73.                 int idx = base + v;
  74.                 if (w[v] < dist[idx]) { dist[idx] = w[v]; pq.push((unsigned)w[v], idx); }
  75.             }
  76.         }
  77.  
  78.         while (!pq.empty()) {
  79.             auto [du, id] = pq.pop();
  80.             if ((int)du != dist[id]) continue;
  81.             int mask = id / N, v = id % N;
  82.  
  83.             uint16_t hv = have[v];
  84.             if (hv) {
  85.                 for (int k = 1; k < S; ++k) if (hv & (1u << k)) {
  86.                     int nm = mask | k, idx = nm * N + v;
  87.                     int nd = (int)du + dist[k * N + v] - w[v];
  88.                     if (nd < dist[idx]) { dist[idx] = nd; pq.push((unsigned)nd, idx); }
  89.                 }
  90.             }
  91.             have[v] |= (1u << mask);
  92.  
  93.             int u = v;
  94.             int nb;
  95.             nb = nei[u][0]; if (nb != -1) { int idx2 = mask * N + nb; int nd = (int)du + w[nb]; if (nd < dist[idx2]) { dist[idx2] = nd; pq.push((unsigned)nd, idx2); } }
  96.             nb = nei[u][1]; if (nb != -1) { int idx2 = mask * N + nb; int nd = (int)du + w[nb]; if (nd < dist[idx2]) { dist[idx2] = nd; pq.push((unsigned)nd, idx2); } }
  97.             nb = nei[u][2]; if (nb != -1) { int idx2 = mask * N + nb; int nd = (int)du + w[nb]; if (nd < dist[idx2]) { dist[idx2] = nd; pq.push((unsigned)nd, idx2); } }
  98.             nb = nei[u][3]; if (nb != -1) { int idx2 = mask * N + nb; int nd = (int)du + w[nb]; if (nd < dist[idx2]) { dist[idx2] = nd; pq.push((unsigned)nd, idx2); } }
  99.         }
  100.  
  101.         int best = INF;
  102.         for (int v = 0; v < N; ++v) best = min(best, dist[15 * N + v]);
  103.         ans = min<long long>(ans, best);
  104.     }
  105.  
  106.     cout << ans << '\n';
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4 7
2753852
9567342
5294979
3180559
stdout
copy 
14
https://ideone.com/9usqK2
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!