fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define vi vector<int>
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define ii pair<int , int>
  9. #define pq priority_queue
  10. #define iii pair<int , pair<int , int>>
  11. #define fo(i,l,r) for(int i=l;i<=r;i++)
  12. #define fod(i,r,l) for(int i=r;i>=l;i--)
  13. #define fill(f,x) memset(f,x,sizeof(f))
  14. #define NAME "file"
  15.  
  16. const int N = 1e3 + 5, mod = 1e9 + 7;
  17. vector <int> g[N*N];
  18. int a[N][N] , p[N*N] , id[N][N] , s[N*N] , d[N*N];
  19. unordered_map <int , bool> mp[N*N];
  20. int n , m;
  21.  
  22. int acs(int u)
  23. {
  24.     if (p[u] == u) return u;
  25.     return p[u] = acs(p[u]);
  26. }
  27. void join(int u , int v)
  28. {
  29.     int x = acs(u);
  30.     int y = acs(v);
  31.     if (x != y)
  32.     {
  33.         p[x] = y;
  34.         s[y] += s[x];
  35.     }
  36. }
  37.  
  38. void bfs()
  39. {
  40.     fo(i, 1, n * m) d[i] = 1e18;
  41.     d[acs(1)] = 0;
  42.     priority_queue <ii , vector <ii> , greater <ii>> q;
  43.     q.push({0 , acs(1)});
  44.  
  45.     while (!q.empty())
  46.     {
  47.         int u = q.top().se;
  48.         int c = q.top().fi;
  49.         q.pop();
  50.         for (auto v : g[u])
  51.         {
  52.             if (d[v] > d[u] + s[v])
  53.             {
  54.                 d[v] = d[u] + s[v];
  55.                 q.push({d[v] , v});
  56.             }
  57.         }
  58.     }
  59. }
  60.  
  61. signed main()
  62. {
  63.     ios_base::sync_with_stdio(0);
  64.     cin.tie(0);  cout.tie(0);
  65.     //freopen(NAME".INP" , "r" , stdin);
  66.     //freopen(NAME".OUT" , "w" , stdout);
  67.  
  68.     cin >> n >> m;
  69.     int cnt = 0;
  70.     fo(i, 1, n)
  71.     fo(j, 1, m)
  72.     {
  73.         cin >> a[i][j];
  74.         if (a[i][j] == 1) a[i][j] = 0;
  75.         id[i][j] = ++cnt;
  76.         p[cnt] = cnt;
  77.         s[cnt] = a[i][j];
  78.     }
  79.  
  80.     fo(i, 1, n)
  81.     fo(j, 1, m)
  82.     {
  83.         if (i + 1 <= n && a[i][j] == a[i + 1][j])
  84.             join(id[i][j] , id[i + 1][j]);
  85.  
  86.         if (j + 1 <= m && a[i][j] == a[i][j + 1])
  87.             join(id[i][j] , id[i][j + 1]);
  88.     }
  89.  
  90.     fo(i, 1, n)
  91.     fo(j, 1, m)
  92.     {
  93.         int u = acs(id[i][j]) , v1 , v2;
  94.         if (i + 1 <= n) v1 = acs(id[i + 1][j]);
  95.         if (j + 1 <= m) v2 = acs(id[i][j + 1]);
  96.  
  97.         if (i + 1 <= n && acs(u) != acs(v1) && !mp[u][v1])
  98.         {
  99.             g[u].push_back(v1);
  100.             g[v1].push_back(u);
  101.             mp[u][v1] = 1;
  102.             mp[v1][u] = 1;
  103.             //cout << u << ' ' << v1 << '\n';
  104.         }
  105.         if (j + 1 <= m && acs(u) != acs(v2) && !mp[u][v2])
  106.         {
  107.             g[u].push_back(v2);
  108.             g[v2].push_back(u);
  109.             mp[u][v2] = 1;
  110.             mp[v2][u] = 1;
  111.             //cout << u << ' ' << v2 << '\n';
  112.         }
  113.     }
  114.  
  115.     bfs();
  116.  
  117.     cout << d[acs(id[n][m])];
  118. }
  119. // haronnee_
Success #stdin #stdout 0.03s 85144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UcPoBf
language:
C++ (gcc 8.3)
created:
23 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!