SHARE
TWEET

CiolCR

a guest Oct 12th, 2017 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3.  
  4. using namespace std;
  5.  
  6. #define LL long long
  7. #define U unsigned
  8. #define ULL U LL
  9. #define P pair
  10. #define F first
  11. #define S second
  12. #define PII P<int, int>
  13. #define PLL P<LL,LL>
  14. #define OS ostream
  15. #define IS istream
  16. #define all(a) a.begin(),a.end()
  17. #define LD long double
  18. #define MB *1024*1024
  19. #define E emplace
  20. #define EB emplace_back
  21. #define PB push_back
  22. #define PF push_front
  23. #define V vector
  24.  
  25. #define FOR(i, a, b) for(decltype(b) i = a; i < b; i++)
  26. #define FORE(i, a, b) for(decltype(b) i = a; i <= b; i++)
  27.  
  28. #ifdef DEBUG
  29.   #define D(...) __VA_ARGS__
  30. #else
  31.   #define D(...)
  32. #endif
  33.  
  34. bool SHOWSTUFF = true;
  35.  
  36. #define SH(...) D(if(SHOWSTUFF){__VA_ARGS__})
  37.  
  38.  
  39.  
  40. template <class A, class B> OS& operator<<(OS& os, const P<A,B> &p){return os << "(" << p.F << "," << p.S << ")";}
  41.  
  42. template <class I> OS& __pisz(OS& os, I a, I b)
  43. {
  44.   if(distance(a, b) == 0)
  45.     return os << "{}";
  46.  
  47.   os << "{";
  48.  
  49.   while(a != b)
  50.     os << *a++ << ' ';
  51.  
  52.   return os << "\b}";
  53. }
  54.  
  55. #define OO(A) template <class... T> OS& operator<<(OS& os, const A<T...> &thing){return __pisz(os, all(thing));}
  56.  
  57. OO(vector) OO(set) OO(deque) OO(map) OO(multiset)
  58.  
  59. template <class I> OS& __piszNl(OS& os, I a, I b)
  60. {
  61.   os << "{\n";
  62.  
  63.   for(I c = a; a != b; a++)
  64.     os << distance(c, a) << ": " << *a << '\n';
  65.  
  66.   return os << "}\n";
  67. }
  68.  
  69.  
  70.  
  71. #define NL SH(cout << endl;)
  72. #define L(a) SH(cout << #a " = " << a << "   ";)
  73. #define LN(a) SH(cout << #a " = " << a << endl;)
  74. #define LOG(a) SH(cout << #a " = ", __piszNl(cout, all(a));)
  75.  
  76. template <class T> T maxi(T a, T b){return (a < b ? b : a);}
  77. template <class T, class... Args> T maxi(T a, Args... args){return maxi(a, maxi(args...));}
  78.  
  79. template <class T> T mini(T a, T b){return (a < b ? a : b);}
  80. template <class T, class... Args> T mini(T a, Args... args){return mini(a, mini(args...));}
  81.  
  82. #define INF ((int)1e9 + 696969)
  83.  
  84. //#######################################################################################################
  85.  
  86. struct xy
  87. {
  88.     int x, y;
  89.     char dir;
  90.  
  91.     xy(){}
  92.     xy(int X, int Y, int DIR = 69) : x(X), y(Y), dir(DIR){}
  93.  
  94.     xy operator+(const xy& other)const {return {x + other.x, y + other.y, dir};}
  95.  
  96.     bool operator<(const xy& other)const{return x < other.x || (x == other.x && y < other.y) || (x == other.x && y == other.y && dir < other.dir);}
  97. };
  98.  
  99. OS& operator<<(OS& os, const xy& p){return os << "(" << p.x << "," << p.y << ")(" << (int)p.dir << ")";}
  100.  
  101.  
  102.  
  103.  
  104. template <class T>
  105. class V2D : public V< V<T> >
  106. {
  107. public:
  108.     using V<V<T> >::resize;
  109.     using V<V<T> >::begin;
  110.     using V<V<T> >::end;
  111.     using V<V<T> >::operator[];
  112.  
  113.     typename V<T>::reference operator[](const xy& pnt){return (*this)[pnt.x][pnt.y];}
  114. };
  115.  
  116.  
  117. V2D<char> plansz;
  118.  
  119. struct wcaleNie4ElementowaTablica{int tab[4]; int& operator[](const char& i){return tab[i];}};
  120.  
  121. V2D< wcaleNie4ElementowaTablica > dist;
  122.  
  123.  
  124.  
  125.  
  126.  
  127. int main()
  128. {
  129.     #ifndef DEBUG
  130.     ios_base::sync_with_stdio(false); cin.tie(0);
  131.     #endif // DEBUG
  132.  
  133.     int w, h;
  134.     cin >> h >> w;
  135.  
  136.     string startDir;
  137.     cin >> startDir;
  138.  
  139.  
  140.     plansz.resize(2 * w + 1, V<char>(2 * h + 1));
  141.     dist.resize(2 * w + 1, V< wcaleNie4ElementowaTablica >(2 * h + 1));
  142.  
  143.     for(int x = 1; x < 2 * w + 1; x += 2)
  144.     for(int y = 1; y < 2 * h + 1; y += 2)
  145.         dist[x][y][0] = dist[x][y][1] = dist[x][y][2] = dist[x][y][3] = INF;
  146.  
  147.  
  148.     xy start, end;
  149.  
  150.     for(int y = 2 * h; y >= 0; y--)
  151.     FOR(x, 0, 2 * w + 1)
  152.     {
  153.         cin >> plansz[x][y];
  154.  
  155.         if(plansz[x][y] == 'S')
  156.             start = {x, y};
  157.  
  158.         if(plansz[x][y] == 'R')
  159.             end = {x, y};
  160.     }
  161.  
  162.  
  163.     if(startDir == "DOL")start.dir = 0;
  164.     if(startDir == "PRAWO")start.dir = 1;
  165.     if(startDir == "GORA")start.dir = 2;
  166.     if(startDir == "LEWO")start.dir = 3;
  167.  
  168.     LOG(plansz)
  169.  
  170.     LN(start)
  171.     LN(end)
  172.  
  173.     set < P<int, xy> > kolej = {{0, start}};
  174.     dist[start][start.dir] = 0;
  175.  
  176.     V<int> dirs = {0, 3, 1, 2};
  177.     V<xy> deltas;
  178.  
  179.     while(!kolej.empty())
  180.     {
  181.         xy v = kolej.begin()->S;
  182.         kolej.erase(kolej.begin());
  183.  
  184.         #define getDelta(d) ((d) == 0 ? xy(0, -1) : (d) == 1 ? xy(1, 0) : (d) == 2 ? xy(0, 1) : xy(-1, 0))
  185.  
  186.         int goCost = 0;
  187.  
  188.         for(auto &d : dirs)
  189.         {
  190.             char curDir = (v.dir + d > 3 ? v.dir + d - 4 : v.dir + d);
  191.             xy curDelt = getDelta(curDir);
  192.  
  193.             xy wall = v + curDelt;
  194.  
  195.             if(plansz[wall] == '-' || plansz[wall] == '|')
  196.                 continue;
  197.  
  198.  
  199.             xy nxt = wall + curDelt;
  200.             nxt.dir = curDir;
  201.  
  202.             if(dist[v][v.dir] + goCost < dist[nxt][curDir])
  203.             {
  204.                 kolej.erase({dist[nxt][curDir], nxt});
  205.  
  206.                 dist[nxt][curDir] = dist[v][v.dir] + goCost;
  207.  
  208.                 kolej.insert({dist[nxt][curDir], nxt});
  209.             }
  210.  
  211.             goCost = 1;
  212.         }
  213.  
  214.     }
  215.  
  216.     int res = mini(dist[end][0], dist[end][1], dist[end][2], dist[end][3]);
  217.  
  218.     cout << (res == INF ? -1 : res) << '\n';
  219.  
  220.     return 0;
  221. }
RAW Paste Data
Top