fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC optimize("O3")
  4. #pragma GCC optimize("O1")
  5. #pragma GCC optimize("O1")
  6. #pragma GCC optimize("unroll-loops")
  7. #pragma GCC optimize(3)
  8. #pragma GCC optimize("Ofast")
  9. #pragma GCC optimize("inline")
  10. #pragma GCC optimize("-fgcse")
  11. #pragma GCC optimize("-fgcse-lm")
  12. #pragma GCC optimize("-fipa-sra")
  13. #pragma GCC optimize("-ftree-pre")
  14. #pragma GCC optimize("-ftree-vrp")
  15. #pragma GCC optimize("-fpeephole2")
  16. #pragma GCC optimize("-ffast-math")
  17. #pragma GCC optimize("-fsched-spec")
  18. #pragma GCC optimize("-falign-jumps")
  19. #pragma GCC optimize("-falign-loops")
  20. #pragma GCC optimize("-falign-labels")
  21. #pragma GCC optimize("-fdevirtualize")
  22. #pragma GCC optimize("-fcaller-saves")
  23. #pragma GCC optimize("-fcrossjumping")
  24. #pragma GCC optimize("-fthread-jumps")
  25. #pragma GCC optimize("-freorder-blocks")
  26. #pragma GCC optimize("-fschedule-insns")
  27. #pragma GCC optimize("inline-functions")
  28. #pragma GCC optimize("-ftree-tail-merge")
  29. #pragma GCC optimize("-fschedule-insns2")
  30. #pragma GCC optimize("-fstrict-aliasing")
  31. #pragma GCC optimize("-falign-functions")
  32. #pragma GCC optimize("-fcse-follow-jumps")
  33. #pragma GCC optimize("-fsched-interblock")
  34. #pragma GCC optimize("-fpartial-inlining")
  35. #pragma GCC optimize("no-stack-protector")
  36. #pragma GCC optimize("-freorder-functions")
  37. #pragma GCC optimize("-findirect-inlining")
  38. #pragma GCC optimize("-fhoist-adjacent-loads")
  39. #pragma GCC optimize("-frerun-cse-after-loop")
  40. #pragma GCC optimize("inline-small-functions")
  41. #pragma GCC optimize("-finline-small-functions")
  42. #pragma GCC optimize("-ftree-switch-conversion")
  43. #pragma GCC optimize("-foptimize-sibling-calls")
  44. #pragma GCC optimize("-fexpensive-optimizations")
  45. #pragma GCC optimize("inline-functions-called-once")
  46. #pragma GCC optimize("-fdelete-null-pointer-checks")
  47. #define int long long
  48. #define cint const int
  49. #define ii pair<int, int>
  50. #define fi first
  51. #define se second
  52. #define vi vector<int>
  53. #define vii vector<vi>
  54. #define pb push_back
  55. #define pq priority_queue
  56. #define mid(l, r) ((l + r) >> 1)
  57. #define left(id) (id << 1)
  58. #define right(id) (id << 1 | 1)
  59. #define cntbit(mask) __builtin_popcountll(mask)
  60. #define BIT(mask, i) (mask & (1ll << (i)))
  61. #define ONBIT(mask, i) (mask | (1ll << (i)))
  62.  
  63. const int MAXN = 115;
  64. const int oo   = 1e18;
  65.  
  66. struct Node {
  67.     int i;
  68.     int j;
  69.     int s;
  70.     int D;
  71. };
  72.  
  73. struct trace {
  74.     int i;
  75.     int j;
  76.     int s;
  77. };
  78.  
  79. struct cmp {
  80.     bool operator() (Node a, Node b) {
  81.         return a.D > b.D;
  82.     }
  83. };
  84.  
  85. int d[MAXN][MAXN][7];
  86. char A[MAXN][MAXN];
  87. trace pre[MAXN][MAXN][7];
  88. bool vis[MAXN][MAXN][7], dg[MAXN][MAXN];
  89. int N, M, X, Y, Z, T;
  90. vector<int> di[7], dj[7], ns[7];
  91.  
  92.  
  93. void djk() {
  94.     for (int i = 1; i <= N; i++) {
  95.         for (int j = 1; j <= M; j++) {
  96.             for (int s = 0; s <= 4; s++) {
  97.                 d[i][j][s] = oo;
  98.                 vis[i][j][s] = 0;
  99.             }
  100.         }
  101.     }
  102.     d[X][Y][0] = 0;
  103.     pq<Node, vector<Node>, cmp> q;
  104.     q.push({X, Y, 0, 0});
  105.     while (q.size()) {
  106.         Node top = q.top();
  107.         q.pop();
  108.         int i = top.i;
  109.         int j = top.j;
  110.         int s = top.s;
  111.         if (vis[i][j][s]) continue;
  112.         vis[i][j][s] = true;
  113.         for (int k = 0; k < 4; k++) {
  114.             int Ni = i + di[s][k];
  115.             int Nj = j + dj[s][k];
  116.             int Ns = ns[s][k];
  117.  
  118.             if (Ni < 1 || Nj < 1 || Ni > N || Nj > M || vis[Ni][Nj][Ns]) continue;
  119.             if (Ns == 0) {
  120.                 if (dg[Ni][Nj]) continue;
  121.             }
  122.  
  123.             if (Ns == 1) {
  124.                 if (dg[Ni][Nj] || dg[Ni + 1][Nj] || dg[Ni + 2][Nj]) continue;
  125.             }
  126.             if (Ns == 2) {
  127.                 if (dg[Ni][Nj] || dg[Ni][Nj - 1] || dg[Ni][Nj - 2]) continue;
  128.             }
  129.  
  130.             if (Ns == 3) {
  131.                 if (dg[Ni][Nj] || dg[Ni - 1][Nj] || dg[Ni - 2][Nj]) continue;
  132.             }
  133.             if (Ns == 4) {
  134.                 if (dg[Ni][Nj] || dg[Ni][Nj + 1] || dg[Ni][Nj + 2]) continue;
  135.             }
  136.             if (d[Ni][Nj][Ns] > d[i][j][s] + 1) {
  137.                 d[Ni][Nj][Ns] = d[i][j][s] + 1;
  138.                 pre[Ni][Nj][Ns] = {i, j, s};
  139.                 //cout << Ni << ' ' << Nj << ' ' << Ns << ' ' << d[Ni][Nj][Ns] << '\n';
  140.                 q.push({Ni, Nj, Ns, d[Ni][Nj][Ns]});
  141.             }
  142.         }
  143.     }
  144. }
  145.  
  146.  
  147.  
  148. signed main() {
  149.     ios_base::sync_with_stdio(0);
  150.     cin.tie(0);
  151.     cout.tie(0);
  152.  
  153. //    freopen("dtqg_gbox_dt2.inp", "r", stdin);
  154. //    freopen("dtqg_gbox_dt2.out", "w", stdout);
  155.  
  156.  
  157.     cin >> N >> M >> X >> Y >> Z >> T;
  158.     X++, Y++, Z++, T++;
  159.     for (int i = 1; i <= N; i++) {
  160.         for (int j = 1; j <= M; j++) {
  161.             cin >> A[i][j];
  162.             if (A[i][j] == '1') dg[i][j] = true;
  163.         }
  164.     }
  165.  
  166.     di[0] = {3, -3, 0, 0};
  167.     dj[0] = {0, 0, -3, 3};
  168.     ns[0] = {3, 1, 4, 2}; // xuong len trai phai
  169.  
  170.     di[1] = {-1, 0, 3, 0};
  171.     dj[1] = {0, 1, 0, -1};
  172.     ns[1] = {0, 1, 0, 1}; // len phai xuong trai
  173.  
  174.     di[2] = {-1, 0, 1, 0};
  175.     dj[2] = {0, 1, 0, -3};
  176.     ns[2] = {2, 0, 2, 0}; // len phai xuong trai
  177.  
  178.     di[3] = {-3, 0, 1, 0};
  179.     dj[3] = {0, 1, 0, -1};
  180.     ns[3] = {0, 3, 0, 3}; // len phai xuong trai
  181.  
  182.     di[4] = {-1, 0, 1, 0};
  183.     dj[4] = {0, 3, 0, -1};
  184.     ns[4] = {4, 0, 4, 0}; // len phai xuong trai
  185.  
  186.     djk();
  187.     if (vis[Z][T][0]) cout << d[Z][T][0] << '\n';
  188.     else {
  189.         cout << -1;
  190.         return 0;
  191.     }
  192.  
  193.     vector<int> res;
  194.     trace a = {Z, T, 0};
  195.     while (a.i != X || a.j != Y || a.s != 0) {
  196.         trace tmp = pre[a.i][a.j][a.s];
  197.         // len tren 3
  198.         // xuong duoi 1
  199.         // sang phai 0
  200.         // sang trai 2
  201.         for (int k = 0; k < 4; k++) {
  202.             int Ni = a.i, Nj = a.j, Ns = a.s;
  203.             int i  = tmp.i, j = tmp.j, s = tmp.s;
  204.             if (Ni == i + di[s][k] && Nj == j + dj[s][k]) {
  205.                 if (s == 0) {
  206.                     if (Ns == 3) res.pb(1);
  207.                     if (Ns == 1) res.pb(3);
  208.                     if (Ns == 4) res.pb(2);
  209.                     if (Ns == 2) res.pb(0);
  210.                 }
  211.                 else {
  212.                     if (k == 0) res.pb(3);
  213.                     if (k == 1) res.pb(0);
  214.                     if (k == 2) res.pb(1);
  215.                     if (k == 3) res.pb(2);
  216.                 }
  217.             }
  218.         }
  219.         a = tmp;
  220.     }
  221.     reverse(res.begin(), res.end());
  222.     for (auto v : res) cout << v << ' ';
  223. }
  224.  
Success #stdin #stdout 0.01s 5656KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/rB98ic
language:
C++14 (gcc 8.3)
created:
10 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!