fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<long long , int>
  10. #define lll pair<long long , pair<long long , long long>>
  11. #define lii pair<long long , pair<int , int>>
  12. #define iii pair<long long , pair<int , int>>
  13. #define iiii pair<pair<long long , int> , pair<int , int>>
  14. #define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
  15. #define li pair<long long , int>
  16. #define db long double
  17. #define onBit(mask , i) (mask | (1 << i))
  18. #define offBit(mask , i) (mask & (~(1 << i)))
  19.  
  20. const int INF = 1e7;
  21. const long long MOD = 998244353;
  22. const int N = 507;
  23. const int MAXN = 2e5 + 5e4 + 7;
  24. const int MAXF = 2300007;
  25.  
  26. int dx[5] = {1 , 0 , -1 , 0};
  27. int dy[5] = {0 , 1 , 0 , -1};
  28.  
  29. char a[N][N];
  30.  
  31. int f[17][MAXN];
  32. int w[MAXN];
  33.  
  34. int n , m;
  35. int res = INF;
  36. vector<int> val[MAXN];
  37.  
  38. int change(int i , int j){
  39.     return m * (i - 1) + j;
  40. }
  41.  
  42. void inp(){
  43.     cin >> n >> m;
  44.  
  45.     for (int i = 1 ; i <= n ; ++i){
  46.         for (int j = 1 ; j <= m ; ++j){
  47.             cin >> a[i][j];
  48.         }
  49.     }
  50. }
  51.  
  52. void steiner(int cur){
  53.  
  54.     const int K = 9;
  55.  
  56.     for (int i = 1 ; i <= n ; ++i){
  57.         for (int j = 1 ; j <= m ; ++j){
  58.  
  59.             int id = change(i , j);
  60.  
  61.             w[id] = abs(a[i][j] - '0' - cur);
  62.  
  63.             for (int mask = 1 ; mask < 16 ; ++mask){
  64.                 f[mask][id] = INF;
  65.             }
  66.  
  67.             if (i == 1) f[1][id] = w[id];
  68.             if (i == n) f[2][id] = w[id];
  69.             if (j == 1) f[4][id] = w[id];
  70.             if (j == m) f[8][id] = w[id];
  71.         }
  72.     }
  73.  
  74.     for (int mask = 1 ; mask < 16 ; ++mask){
  75.  
  76.         for (int sub = (mask - 1) & mask ; sub ; sub = (sub - 1) & mask){
  77.             if (sub > (sub ^ mask)){
  78.  
  79.                 for (int i = 1 ; i <= n ; ++i){
  80.                     for (int j = 1 ; j <= m ; ++j){
  81.  
  82.                         int id = change(i , j);
  83.  
  84.                         f[mask][id] = min(
  85.                             f[mask][id],
  86.                             f[sub][id] + f[sub ^ mask][id] - w[id]
  87.                         );
  88.                     }
  89.                 }
  90.             }
  91.         }
  92.  
  93.         if (mask == 15){
  94.  
  95.             for (int i = 1 ; i <= n ; ++i){
  96.                 for (int j = 1 ; j <= m ; ++j){
  97.  
  98.                     res = min(
  99.                         res ,
  100.                         f[15][change(i , j)]
  101.                     );
  102.                 }
  103.             }
  104.  
  105.             return;
  106.         }
  107.  
  108.         vector<int> bucket[K + 1];
  109.  
  110.         int num = 0;
  111.  
  112.         for (int i = 1 ; i <= n ; ++i){
  113.             for (int j = 1 ; j <= m ; ++j){
  114.  
  115.                 int id = change(i , j);
  116.                 if (f[mask][id] > 9 * K) continue;
  117.                 num++;
  118.                 if (f[mask][id] <= K){
  119.  
  120.                     bucket[f[mask][id]].push_back(id);
  121.                 }
  122.  
  123.                 else val[f[mask][id]].push_back(id);
  124.             }
  125.         }
  126.  
  127.         int pos = 0;
  128.  
  129.         while (num){
  130.             while (bucket[pos % (K + 1)].empty() && val[pos].empty()){
  131.                 pos++;
  132.             }
  133.  
  134.             while (val[pos].size()){
  135.                 bucket[pos % (K + 1)].push_back(val[pos].back());
  136.                 val[pos].pop_back();
  137.             }
  138.  
  139.             int id = bucket[pos % (K + 1)].back();
  140.             bucket[pos % (K + 1)].pop_back();
  141.  
  142.             num--;
  143.  
  144.             if (f[mask][id] != pos){
  145.                 continue;
  146.             }
  147.  
  148.             int r = (id - 1) / m + 1;
  149.             int c = (id - 1) % m + 1;
  150.  
  151.             for (int k = 0 ; k < 4 ; ++k){
  152.  
  153.                 int u = r + dx[k];
  154.                 int v = c + dy[k];
  155.  
  156.                 if (u < 1 || u > n || v < 1 || v > m) continue;
  157.  
  158.                 int nid = change(u , v);
  159.  
  160.                 int nd = f[mask][id] + w[nid];
  161.  
  162.                 if (nd < f[mask][nid]){
  163.  
  164.                     f[mask][nid] = nd;
  165.  
  166.                     bucket[nd % (K + 1)].push_back(nid);
  167.  
  168.                     num++;
  169.                 }
  170.             }
  171.         }
  172.     }
  173. }
  174.  
  175. void solve(){
  176.  
  177.     for (int cur = 0 ; cur <= 9 ; ++cur){
  178.         steiner(cur);
  179.     }
  180.  
  181.     cout << res;
  182. }
  183.  
  184. int main(){
  185. //    freopen("difmax.inp" , "r" , stdin);
  186. //    freopen("difmax.out" , "w" , stdout);
  187.     faster;
  188.     inp();
  189.     solve();
  190.     return 0;
  191. }
  192.  
Success #stdin #stdout 0.01s 10576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10000000
https://ideone.com/RIhurV
language:
C++14 (gcc 8.3)
created:
3 days 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!