fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. const int INF = 1e8;
  9. const int MAX_DIST = 100005;
  10. const int MAX_Q = 5000005;
  11.  
  12. int head[MAX_DIST];
  13. int q_u[MAX_Q];
  14. int q_nxt[MAX_Q];
  15. int q_ptr = 0;
  16. int min_d = 0;
  17. int max_d_pushed = -1;
  18.  
  19. void init_dijkstra() {
  20.     if (max_d_pushed >= 0) {
  21.         for (int i = 0; i <= max_d_pushed; ++i) head[i] = -1;
  22.     } else {
  23.         for (int i = 0; i < MAX_DIST; ++i) head[i] = -1;
  24.     }
  25.     q_ptr = 0;
  26.     min_d = INF;
  27.     max_d_pushed = -1;
  28. }
  29.  
  30. inline void push_node(int d, int u) {
  31.     if (d >= MAX_DIST) return;
  32.     q_u[q_ptr] = u;
  33.     q_nxt[q_ptr] = head[d];
  34.     head[d] = q_ptr;
  35.     q_ptr++;
  36.     if (d < min_d) min_d = d;
  37.     if (d > max_d_pushed) max_d_pushed = d;
  38. }
  39.  
  40. int N, M;
  41. string grid[505];
  42. int weight[250005];
  43. int dT[250005], dB[250005], dL[250005], dR[250005];
  44. int dTL[250005], dTR[250005], dTB[250005];
  45.  
  46. int dx[] = {-1, 1, 0, 0};
  47. int dy[] = {0, 0, -1, 1};
  48.  
  49. void dijkstra(int* dist) {
  50.     init_dijkstra();
  51.     for (int i = 0; i < N * M; ++i) {
  52.         if (dist[i] != INF) {
  53.             push_node(dist[i], i);
  54.         }
  55.     }
  56.  
  57.     while (min_d <= max_d_pushed) {
  58.         int p = head[min_d];
  59.         if (p == -1) {
  60.             min_d++;
  61.             continue;
  62.         }
  63.         head[min_d] = q_nxt[p];
  64.  
  65.         int u = q_u[p];
  66.         int d = min_d;
  67.  
  68.         if (d > dist[u]) continue;
  69.  
  70.         int r = u / M;
  71.         int c = u % M;
  72.  
  73.         for (int i = 0; i < 4; ++i) {
  74.             int nr = r + dx[i];
  75.             int nc = c + dy[i];
  76.  
  77.             if (nr >= 0 && nr < N && nc >= 0 && nc < M) {
  78.                 int v = nr * M + nc;
  79.                 int new_d = d + weight[v];
  80.                 if (dist[v] > new_d) {
  81.                     dist[v] = new_d;
  82.                     push_node(new_d, v);
  83.                 }
  84.             }
  85.         }
  86.     }
  87. }
  88.  
  89. int main() {
  90.     ios_base::sync_with_stdio(false);
  91.     cin.tie(NULL);
  92.  
  93.     if (!(cin >> N >> M)) return 0;
  94.     for (int i = 0; i < N; ++i) {
  95.         cin >> grid[i];
  96.     }
  97.  
  98.     int min_total_cost = INF;
  99.  
  100.     for (int D = 0; D <= 9; ++D) {
  101.         for (int r = 0; r < N; ++r) {
  102.             for (int c = 0; c < M; ++c) {
  103.                 weight[r * M + c] = abs((grid[r][c] - '0') - D);
  104.                 dT[r * M + c] = INF;
  105.                 dB[r * M + c] = INF;
  106.                 dL[r * M + c] = INF;
  107.                 dR[r * M + c] = INF;
  108.             }
  109.         }
  110.  
  111.         for (int c = 0; c < M; ++c) {
  112.             dT[0 * M + c] = weight[0 * M + c];
  113.             dB[(N - 1) * M + c] = weight[(N - 1) * M + c];
  114.         }
  115.         for (int r = 0; r < N; ++r) {
  116.             dL[r * M + 0] = weight[r * M + 0];
  117.             dR[r * M + (M - 1)] = weight[r * M + (M - 1)];
  118.         }
  119.  
  120.         dijkstra(dT);
  121.         dijkstra(dB);
  122.         dijkstra(dL);
  123.         dijkstra(dR);
  124.  
  125.         for (int i = 0; i < N * M; ++i) {
  126.             dTL[i] = dT[i] + dL[i] - weight[i];
  127.             dTR[i] = dT[i] + dR[i] - weight[i];
  128.             dTB[i] = dT[i] + dB[i] - weight[i];
  129.         }
  130.  
  131.         dijkstra(dTL);
  132.         dijkstra(dTR);
  133.         dijkstra(dTB);
  134.  
  135.         for (int i = 0; i < N * M; ++i) {
  136.             int cost1 = dTL[i] + dB[i] + dR[i] - 2 * weight[i];
  137.             int cost2 = dTR[i] + dB[i] + dL[i] - 2 * weight[i];
  138.             int cost3 = dTB[i] + dL[i] + dR[i] - 2 * weight[i];
  139.  
  140.             if (cost1 < min_total_cost) min_total_cost = cost1;
  141.             if (cost2 < min_total_cost) min_total_cost = cost2;
  142.             if (cost3 < min_total_cost) min_total_cost = cost3;
  143.         }
  144.     }
  145.  
  146.     cout << min_total_cost << "\n";
  147.     return 0;
  148. }
Success #stdin #stdout 0.01s 14216KB
comments (?)
stdin
copy 
4 7
2753852
9567342
5294979
3180559
stdout
copy 
14
https://ideone.com/zKI0Nf
language:
C++14 (gcc 8.3)
created:
4 hours 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!