fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
  4. #define MASK(i) (1LL<<(i))
  5.  
  6. const int N=305;
  7. const int INF=1e9;
  8.  
  9. int m,n;
  10. char a[N][N];
  11. int dis[N][N][16];
  12. int cost[N][N];
  13.  
  14. const int dx[]={-1,1,0,0};
  15. const int dy[]={0,0,-1,1};
  16. const int north=0;
  17. const int south=3;
  18. const int west=1;
  19. const int east=2;
  20.  
  21. struct state
  22. {
  23.     int d,x,y;
  24.     bool operator > (const state &o) const 
  25.     {
  26.         return d>o.d;
  27.     }
  28. };
  29.  
  30. int dijkstra(int s)
  31. {
  32.     FOR(i,1,m)
  33.     FOR(j,1,n)
  34.     {
  35.         cost[i][j]=abs(a[i][j]-'0'-s);
  36.         FOR(mask,0,15) dis[i][j][mask]=INF;
  37.     }
  38.  
  39.     FOR(i,1,m)
  40.     FOR(j,1,n)
  41.     {
  42.         int base_mask=0;
  43.         if (i==1) base_mask|=MASK(north);
  44.         if (j==1) base_mask|=MASK(west);
  45.         if (i==m) base_mask|=MASK(south);
  46.         if (j==n) base_mask|=MASK(east);
  47.  
  48.         dis[i][j][base_mask]=cost[i][j];
  49.         for(int sub=base_mask;sub>0;sub=(sub-1)&base_mask)
  50.         {
  51.             if (dis[i][j][sub] > cost[i][j]) dis[i][j][sub] = cost[i][j];
  52.         }
  53.         dis[i][j][0]=cost[i][j];
  54.     }
  55.  
  56.     priority_queue<state,vector<state>,greater<state>> pq;
  57.  
  58.     FOR(mask,1,15)
  59.     {
  60.         for(int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) 
  61.         {
  62.             int complement = mask ^ sub;
  63.             if (sub < complement) continue;
  64.             FOR(i,1,m)
  65.             FOR(j,1,n)
  66.             {
  67.                 if (dis[i][j][sub] < INF && dis[i][j][complement] < INF)
  68.                 {
  69.                     long long val = dis[i][j][sub] + dis[i][j][complement] - cost[i][j];
  70.                     if (dis[i][j][mask] > val) dis[i][j][mask] = val;
  71.                 }
  72.             }
  73.         }
  74.         FOR(i,1,m)
  75.         FOR(j,1,n)
  76.         {
  77.             if (dis[i][j][mask] < INF) pq.push({dis[i][j][mask],i,j});
  78.         }
  79.         while(!pq.empty())
  80.         {
  81.             int d=pq.top().d,x=pq.top().x,y=pq.top().y;
  82.             pq.pop();
  83.  
  84.             if (d>dis[x][y][mask]) continue;
  85.  
  86.             FOR(k,0,3)
  87.             {
  88.                 int nx=x+dx[k];
  89.                 int ny=y+dy[k];
  90.                 if (nx>=1&&nx<=m&&ny>=1&&ny<=n)
  91.                 {
  92.                     if (dis[nx][ny][mask] > d + cost[nx][ny])
  93.                     {
  94.                         dis[nx][ny][mask] = d + cost[nx][ny];
  95.                         pq.push({dis[nx][ny][mask],nx,ny});
  96.                     }
  97.                 }
  98.             }
  99.         }
  100.     }
  101.  
  102.     int ans=INF;
  103.     FOR(i,1,m) FOR(j,1,n) if (ans > dis[i][j][15]) ans = dis[i][j][15];
  104.     return ans;
  105. }
  106.  
  107. int32_t main()
  108. {
  109.     ios_base::sync_with_stdio(0);
  110.     cin.tie(0);cout.tie(0);
  111.     int t;
  112.     if (cin>>t)
  113.     {
  114.         while(t--)
  115.         {
  116.             cin>>m>>n;
  117.             FOR(i,1,m)
  118.             FOR(j,1,n) cin>>a[i][j];
  119.  
  120.             int ans=INF;
  121.             FOR(s,0,9) {
  122.                 int res = dijkstra(s);
  123.                 if (ans > res) ans = res;
  124.             }
  125.             cout<<ans<<'\n';
  126.         }
  127.     }
  128.     return 0;
  129. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FMr8OR
language:
C++14 (gcc 8.3)
created:
4 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!