fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3. const int inf = 1e9 + 7;
  4. int n, m;
  5. int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
  6. int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};
  7. struct node {
  8.     int dif, x, y;
  9.     bool operator<(const node &other) const {
  10.         return dif > other.dif;
  11.     }
  12. };
  13. bool ok(int x, int y) {
  14.     return  x >= 1 && x <= n && y >= 1 && y <= m;
  15. }
  16. vector<vector<int>> dijkstra(int x, int y, vector<vector<char>> a) {
  17.     vector<vector<int>> dist(n + 5, vector<int> (m + 5, inf));
  18.     dist[x][y] = (a[x][y] == '#' ? 0 : (a[x][y] - '0'));
  19.     priority_queue<node> q;
  20.     q.push({dist[x][y], x, y});
  21.     while (q.size()) {
  22.         int x = q.top().x;
  23.         int y = q.top().y;
  24.         int dif = q.top().dif;
  25.         q.pop();
  26.         if (dif > dist[x][y]) continue;
  27.         for (int d = 0; d < 8; d++) {
  28.             int nx = x + dx[d];
  29.             int ny = y + dy[d];
  30.             if (!ok(nx, ny)) continue;
  31.             if (a[nx][ny] == '.') continue;
  32.             int add = a[nx][ny] == '#' ? 0 : (a[nx][ny] - '0');
  33.             if (dist[nx][ny] > dist[x][y] + add) {
  34.                 dist[nx][ny] = dist[x][y] + add;
  35.                 q.push({dist[nx][ny], nx, ny}); 
  36.             }
  37.         }
  38.     }
  39.     return dist;
  40. }
  41. int main() {
  42.     ios::sync_with_stdio(false);
  43.     cin.tie(0);
  44.     cin >> n >> m;
  45.     vector<vector<char>> a(n + 5, vector<char> (m + 5, 0));
  46.     for (int i = 1; i <= n; i++) {
  47.         for (int j = 1; j <= m; j++) {
  48.             cin >> a[i][j]; 
  49.         }
  50.     } 
  51.     int ans = inf; 
  52.     for (int i = 1; i <= m; i++) {
  53.         if (a[1][i] == '.') continue;
  54.         vector<vector<int>> dist = dijkstra(1, i, a);
  55.         for (int j = 2; j <= n; j++) ans = min(ans, dist[j][1]);
  56.         for (int j = 1; j <= m; j++) ans = min(ans, dist[n][j]);
  57.     }
  58.     for (int j = 1; j <= m; j++) {
  59.         if (a[n][j] == '.') continue;
  60.         vector<vector<int>> dist = dijkstra(n, j, a);
  61.         for (int i = 1; i <= n; ++i) ans = min(ans, dist[i][m]);
  62.     }
  63.     for (int i = 1; i <= n; i++) {
  64.         if (a[i][1] == '.') continue;
  65.         vector<vector<int>> dist = dijkstra(i, 1, a);
  66.         for (int j = 1; j <= n; j++) ans = min(ans, dist[j][m]);
  67.     }
  68.     cout << ans << '\n'; 
  69.     return 0;
  70. }
  71.  
  72. /*
  73. break
  74. could
  75. misty
  76. phone
  77. deads
  78. */
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000007
https://ideone.com/Dm9gDS
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!