fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<ll, ll>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. struct Node
  12. {
  13.     int x, y, k;
  14.     ll dist;
  15.  
  16.     Node(int x = 0, int y = 0, int k = 0, ll dist = 0) :
  17.         x(x), y(y), k(k), dist(dist) {};
  18.     bool operator > (const Node &other) const
  19.     {
  20.         return dist > other.dist;
  21.     }
  22. };
  23. struct Parent
  24. {
  25.     int x, y, k, type;
  26.  
  27.     Parent(int x = 0, int y = 0, int k = 0, int type = 0) :
  28.         x(x), y(y), k(k), type(type) {};
  29. };
  30.  
  31. const int maxn = 1e2;
  32. const ll INF = 1e18;
  33. const int dx[4][4] =
  34. {
  35.     {0, 1, 0, 0},
  36.     {1, 1, 0, 0},
  37.     {0, -1, 0, 0},
  38.     {-1, -1, 0, 0}
  39. };
  40. const int dy[4][4] =
  41. {
  42.     {1, 1, 0, 0},
  43.     {0, -1, 0, 0},
  44.     {-1, -1, 0, 0},
  45.     {0, 1, 0, 0}
  46. };
  47. const int dk[4][4] =
  48. {
  49.     {0, 0, 1, 3},
  50.     {1, 1, 2, 0},
  51.     {2, 2, 3, 1},
  52.     {3, 3, 0, 2}
  53. };
  54.  
  55. int n, m, x, y, z, t;
  56. Parent p[maxn + 10][maxn + 10][4];
  57. ll w[4], d[maxn + 10][maxn + 10][4];
  58. bool vis[maxn + 10][maxn + 10];
  59. priority_queue<Node, vector<Node>, greater<Node>> pq;
  60. vector<int> trace;
  61. ii ans = {INF , INF};
  62.  
  63. bool in_matrix(int x, int y)
  64. {
  65.     return x >= 1 && x <= n && y >= 1 && y <= m;
  66. }
  67.  
  68. int main()
  69. {
  70.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  71.     if (fopen("FROBOT.INP", "r"))
  72.     {
  73.         freopen("FROBOT.INP", "r", stdin);
  74.         freopen("FROBOT.OUT", "w", stdout);
  75.     }
  76.  
  77.     cin >> n >> m >> x >> y >> z >> t;
  78.     for (int i = 0; i < 4; i++)
  79.         cin >> w[i];
  80.     for (int i = 1; i <= n; i++)
  81.         for (int j = 1; j <= m; j++)
  82.         {
  83.             char c;
  84.             cin >> c;
  85.             vis[i][j] = c - '0';
  86.         }
  87.     for (int i = 1; i <= n; i++)
  88.         for (int j = 1; j <= m; j++)
  89.             for (int k = 0; k < 4; k++)
  90.                 d[i][j][k] = INF;
  91.     d[x][y][0] = 0;
  92.     pq.push(Node(x, y, 0, 0));
  93.     while (pq.size())
  94.     {
  95.         auto [x, y, k, dist] = pq.top();
  96.         pq.pop();
  97.         if (dist > d[x][y][k])
  98.             continue;
  99.         for (int i = 0; i < 4; i++)
  100.         {
  101.             int nx_x = x + dx[k][i];
  102.             int nx_y = y + dy[k][i];
  103.             int nx_k = dk[k][i];
  104.             if (!in_matrix(nx_x, nx_y) || vis[nx_x][nx_y])
  105.                 continue;
  106.             if (d[nx_x][nx_y][nx_k] > d[x][y][k] + w[i])
  107.             {
  108.                 d[nx_x][nx_y][nx_k] = d[x][y][k] + w[i];
  109.                 p[nx_x][nx_y][nx_k] = Parent(x, y, k, i + 1);
  110.                 pq.push(Node(nx_x, nx_y, nx_k, d[nx_x][nx_y][nx_k]));
  111.             }
  112.         }
  113.     }
  114.     for (int i = 0; i < 4; i++)
  115.         ans = min(ans, {d[z][t][i], i});
  116.     if (ans.fi == INF)
  117.         return cout << -1, 0;
  118.     int dir = ans.se;
  119.     while (z && t)
  120.     {
  121.         auto [x, y, k, type] = p[z][t][dir];
  122.         if (type)
  123.             trace.push_back(type);
  124.         z = x;
  125.         t = y;
  126.         dir = k;
  127.     }
  128.     reverse(trace.begin(), trace.end());
  129.     cout << ans.fi, el;
  130.     cout << trace.size(), el;
  131.     for (int x : trace)
  132.         cout << x << ' ';
  133. }
  134.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
https://ideone.com/biXKfy
language:
C++14 (gcc 8.3)
created:
14 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!