fork download
copy 
  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 pb push_back
  49.  
  50. const int MAXN = 115;
  51. const int oo   = 1e18;
  52.  
  53. struct Node {
  54.     int i;
  55.     int j;
  56.     int s;
  57.     int D;
  58. };
  59.  
  60. struct trace {
  61.     int i;
  62.     int j;
  63.     int s;
  64. };
  65.  
  66. struct cmp {
  67.     bool operator() (const Node &a, const Node &b) const {
  68.         return a.D > b.D;
  69.     }
  70. };
  71.  
  72. int d[MAXN][MAXN][7];
  73. char A[MAXN][MAXN];
  74. trace pre[MAXN][MAXN][7];
  75. int premove[MAXN][MAXN][7];
  76. bool vis[MAXN][MAXN][7], dg[MAXN][MAXN];
  77. int N, M, X, Y, Z, T;
  78. vector<int> di[7], dj[7], ns[7];
  79.  
  80. inline bool inside(int Ni, int Nj, int Ns) {
  81.     if (Ni < 1 || Nj < 1 || Ni > N || Nj > M) return false;
  82.     if (Ns == 0) return true;
  83.     if (Ns == 1) return (Ni + 2 <= N);
  84.     if (Ns == 2) return (Nj - 2 >= 1);
  85.     if (Ns == 3) return (Ni - 2 >= 1);
  86.     if (Ns == 4) return (Nj + 2 <= M);
  87.     return false;
  88. }
  89.  
  90. void djk() {
  91.     for (int i = 1; i <= N; i++) {
  92.         for (int j = 1; j <= M; j++) {
  93.             for (int s = 0; s <= 4; s++) {
  94.                 d[i][j][s] = oo;
  95.                 vis[i][j][s] = false;
  96.                 premove[i][j][s] = -1;
  97.                 pre[i][j][s] = {0,0,0};
  98.             }
  99.         }
  100.     }
  101.     d[X][Y][0] = 0;
  102.     priority_queue<Node, vector<Node>, cmp> q;
  103.     q.push({X, Y, 0, 0});
  104.     while (!q.empty()) {
  105.         Node top = q.top();
  106.         q.pop();
  107.         int i = top.i;
  108.         int j = top.j;
  109.         int s = top.s;
  110.         if (vis[i][j][s]) continue;
  111.         vis[i][j][s] = true;
  112.         for (int k = 0; k < 4; k++) {
  113.             int Ni = i + di[s][k];
  114.             int Nj = j + dj[s][k];
  115.             int Ns = ns[s][k];
  116.             if (!inside(Ni, Nj, Ns) || vis[Ni][Nj][Ns]) continue;
  117.             bool blocked = false;
  118.             if (Ns == 0) {
  119.                 if (dg[Ni][Nj]) blocked = true;
  120.             } else if (Ns == 1) {
  121.                 if (dg[Ni][Nj] || dg[Ni + 1][Nj] || dg[Ni + 2][Nj]) blocked = true;
  122.             } else if (Ns == 2) {
  123.                 if (dg[Ni][Nj] || dg[Ni][Nj - 1] || dg[Ni][Nj - 2]) blocked = true;
  124.             } else if (Ns == 3) {
  125.                 if (dg[Ni][Nj] || dg[Ni - 1][Nj] || dg[Ni - 2][Nj]) blocked = true;
  126.             } else if (Ns == 4) {
  127.                 if (dg[Ni][Nj] || dg[Ni][Nj + 1] || dg[Ni][Nj + 2]) blocked = true;
  128.             }
  129.             if (blocked) continue;
  130.             if (d[Ni][Nj][Ns] > d[i][j][s] + 1) {
  131.                 d[Ni][Nj][Ns] = d[i][j][s] + 1;
  132.                 pre[Ni][Nj][Ns] = {i, j, s};
  133.                 int outmove = -1;
  134.                 if (s == 0) {
  135.                     if (Ns == 3) outmove = 1;
  136.                     else if (Ns == 1) outmove = 3;
  137.                     else if (Ns == 4) outmove = 2;
  138.                     else if (Ns == 2) outmove = 0;
  139.                 } else {
  140.                     if (k == 0) outmove = 3;
  141.                     else if (k == 1) outmove = 0;
  142.                     else if (k == 2) outmove = 1;
  143.                     else if (k == 3) outmove = 2;
  144.                 }
  145.                 premove[Ni][Nj][Ns] = outmove;
  146.                 q.push({Ni, Nj, Ns, (int)d[Ni][Nj][Ns]});
  147.             }
  148.         }
  149.     }
  150. }
  151.  
  152. signed main() {
  153.     ios::sync_with_stdio(false);
  154.     cin.tie(nullptr);
  155.     cin >> N >> M >> X >> Y >> Z >> T;
  156.     X++; Y++; Z++; T++;
  157.     memset(dg, 0, sizeof(dg));
  158.     for (int i = 1; i <= N; i++) {
  159.         for (int j = 1; j <= M; j++) {
  160.             cin >> A[i][j];
  161.             if (A[i][j] == '1') dg[i][j] = true;
  162.         }
  163.     }
  164.  
  165.     di[0] = {3, -3, 0, 0};
  166.     dj[0] = {0, 0, -3, 3};
  167.     ns[0] = {3, 1, 4, 2};
  168.  
  169.     di[1] = {-1, 0, 3, 0};
  170.     dj[1] = {0, 1, 0, -1};
  171.     ns[1] = {0, 1, 0, 1};
  172.  
  173.     di[2] = {-1, 0, 1, 0};
  174.     dj[2] = {0, 1, 0, -3};
  175.     ns[2] = {2, 0, 2, 0};
  176.  
  177.     di[3] = {-3, 0, 1, 0};
  178.     dj[3] = {0, 1, 0, -1};
  179.     ns[3] = {0, 3, 0, 3};
  180.  
  181.     di[4] = {-1, 0, 1, 0};
  182.     dj[4] = {0, 3, 0, -1};
  183.     ns[4] = {4, 0, 4, 0};
  184.  
  185.     djk();
  186.     if (!vis[Z][T][0]) {
  187.         cout << -1 << '\n';
  188.         return 0;
  189.     }
  190.     cout << d[Z][T][0] << '\n';
  191.  
  192.     vector<int> res;
  193.     trace a = {Z, T, 0};
  194.     while (!(a.i == X && a.j == Y && a.s == 0)) {
  195.         int mv = premove[a.i][a.j][a.s];
  196.         if (mv == -1) break;
  197.         res.pb(mv);
  198.         trace tmp = pre[a.i][a.j][a.s];
  199.         a = tmp;
  200.     }
  201.     reverse(res.begin(), res.end());
  202.     for (size_t idx = 0; idx < res.size(); ++idx) {
  203.         if (idx) cout << ' ';
  204.         cout << res[idx];
  205.     }
  206.     if (!res.empty()) cout << '\n';
  207.     return 0;
  208. }
  209.  
  210.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/oqDfaZ
language:
C++14 (gcc 8.3)
created:
14 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!