fork download
copy 
  1. /**
  2.  *    author:  mamion
  3.  *    created: Saturday 2024-10-26
  4. **/
  5.  
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #ifdef LOCAL
  10. #include<cpp-dump-main/cpp-dump.hpp>
  11. #define debug(...) cpp_dump(__VA_ARGS__)
  12. CPP_DUMP_SET_OPTION_GLOBAL(max_line_width, 100);
  13. CPP_DUMP_SET_OPTION_GLOBAL(log_label_func, cpp_dump::log_label::filename());
  14. CPP_DUMP_SET_OPTION_GLOBAL(enable_asterisk, true);
  15. #else
  16. #define debug(...)
  17. #endif // LOCAL
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef long double ld;
  22.  
  23. int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
  24. int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
  25.  
  26. const int N = 2e5 + 100;
  27. int m, n, d[N], ans;
  28. char c[N];
  29.  
  30. inline int get(int x, int y) {
  31.     return (x - 1) * n + y;
  32. }
  33.  
  34. void dijkstra(int state) {
  35.     memset(d, 0x3f, sizeof d);
  36.     priority_queue<pair<int, pair<int, int>>> pq;
  37.  
  38.     if (state == 0)
  39.         for (int i = 1; i <= n; i++) {
  40.             int ij = get(1, i);
  41.             if ('0' <= c[ij] && c[ij] <= '9')
  42.                 d[ij] = c[ij] - '0', pq.push({-d[ij], {1, i}});
  43.         }
  44.  
  45.     if (state == 1)
  46.         for (int i = 1; i <= m; i++) {
  47.             int ij = get(i, 1);
  48.             if ('0' <= c[ij] && c[ij] <= '9')
  49.                 d[ij] = c[ij] - '0', pq.push({-d[ij], {i, 1}});
  50.         }
  51.  
  52.     while (pq.size()) {
  53.         int dist, u, v, uv;
  54.         dist = -pq.top().first; tie(u, v) = pq.top().second; pq.pop();
  55.         uv = get(u, v);
  56.         if (dist != d[uv]) continue;
  57.         for (int i = 0; i < 8; i++) {
  58.             int x = u + dx[i], y = v + dy[i];
  59.             if (x < 1 || m < x) continue;
  60.             if (y < 1 || n < y) continue;
  61.             int xy = get(x, y);
  62.             if (c[xy] < '0' || '9' < c[xy]) continue;
  63.             if (d[xy] > d[uv] + c[xy] - '0') {
  64.                 d[xy] = d[uv] + c[xy] - '0';
  65.                 pq.push({-d[xy], {x, y}});
  66.             }
  67.         }
  68.     }
  69.  
  70.     if (state == 0) {
  71.         for (int i = 1; i <= n; i++) {
  72.             int ij = get(m, i);
  73.             ans = min(ans, d[ij]);
  74.         }
  75.         for (int i = 1; i <= m; i++) {
  76.             int ij = get(i, 1);
  77.             ans = min(ans, d[ij]);
  78.         }
  79.     }
  80.     if (state == 1) {
  81.         for (int i = 1; i <= n; i++) {
  82.             int ij = get(1, i);
  83.             ans = min(ans, d[ij]);
  84.         }
  85.         for (int i = 1; i <= m; i++) {
  86.             int ij = get(i, n);
  87.             ans = min(ans, d[ij]);
  88.         }
  89.     }
  90. }
  91.  
  92. void solve() {
  93.     cin >> m >> n;
  94.     for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) {
  95.         int ij = get(i, j);
  96.         cin >> c[ij];
  97.         if (c[ij] == '#') c[ij] = '0';
  98.     }
  99.     ans = 1e9;
  100.     dijkstra(0);
  101.     dijkstra(1);
  102.     cout << (ans == 1e9 ? -1 : ans);
  103. }
  104.  
  105. int main() {
  106.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  107.  
  108. #ifdef LOCAL
  109.     freopen("main.inp", "r", stdin);
  110.     freopen("main.out", "w", stdout);
  111. #else
  112.     #define file "name"
  113.     if (fopen(file".inp", "r")) {
  114.         freopen(file".inp", "r", stdin);
  115.         freopen(file".out", "w", stdout);
  116.     }
  117. #endif // LOCAL
  118.  
  119.     int T; T = 1; if (0) cin >> T;
  120.     for (int i = 1; i <= T; i++)
  121.     {
  122.         solve();
  123.     }
  124. }
  125.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/vLDQaC
language:
C++14 (gcc 8.3)
created:
6 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!