Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define LL long long
- #define U unsigned
- #define ULL U LL
- #define P pair
- #define F first
- #define S second
- #define PII P<int, int>
- #define PLL P<LL,LL>
- #define OS ostream
- #define IS istream
- #define all(a) a.begin(),a.end()
- #define LD long double
- #define MB *1024*1024
- #define E emplace
- #define EB emplace_back
- #define PB push_back
- #define PF push_front
- #define V vector
- #define FOR(i, a, b) for(decltype(b) i = a; i < b; i++)
- #define FORE(i, a, b) for(decltype(b) i = a; i <= b; i++)
- #ifdef DEBUG
- #define D(...) __VA_ARGS__
- #else
- #define D(...)
- #endif
- bool SHOWSTUFF = true;
- #define SH(...) D(if(SHOWSTUFF){__VA_ARGS__})
- template <class A, class B> OS& operator<<(OS& os, const P<A,B> &p){return os << "(" << p.F << "," << p.S << ")";}
- template <class I> OS& __pisz(OS& os, I a, I b)
- {
- if(distance(a, b) == 0)
- return os << "{}";
- os << "{";
- while(a != b)
- os << *a++ << ' ';
- return os << "\b}";
- }
- #define OO(A) template <class... T> OS& operator<<(OS& os, const A<T...> &thing){return __pisz(os, all(thing));}
- OO(vector) OO(set) OO(deque) OO(map) OO(multiset)
- template <class I> OS& __piszNl(OS& os, I a, I b)
- {
- os << "{\n";
- for(I c = a; a != b; a++)
- os << distance(c, a) << ": " << *a << '\n';
- return os << "}\n";
- }
- #define NL SH(cout << endl;)
- #define L(a) SH(cout << #a " = " << a << " ";)
- #define LN(a) SH(cout << #a " = " << a << endl;)
- #define LOG(a) SH(cout << #a " = ", __piszNl(cout, all(a));)
- template <class T> T maxi(T a, T b){return (a < b ? b : a);}
- template <class T, class... Args> T maxi(T a, Args... args){return maxi(a, maxi(args...));}
- template <class T> T mini(T a, T b){return (a < b ? a : b);}
- template <class T, class... Args> T mini(T a, Args... args){return mini(a, mini(args...));}
- #define INF ((int)1e9 + 696969)
- //#######################################################################################################
- struct xy
- {
- int x, y;
- char dir;
- xy(){}
- xy(int X, int Y, int DIR = 69) : x(X), y(Y), dir(DIR){}
- xy operator+(const xy& other)const {return {x + other.x, y + other.y, dir};}
- 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);}
- };
- OS& operator<<(OS& os, const xy& p){return os << "(" << p.x << "," << p.y << ")(" << (int)p.dir << ")";}
- template <class T>
- class V2D : public V< V<T> >
- {
- public:
- using V<V<T> >::resize;
- using V<V<T> >::begin;
- using V<V<T> >::end;
- using V<V<T> >::operator[];
- typename V<T>::reference operator[](const xy& pnt){return (*this)[pnt.x][pnt.y];}
- };
- V2D<char> plansz;
- struct wcaleNie4ElementowaTablica{int tab[4]; int& operator[](const char& i){return tab[i];}};
- V2D< wcaleNie4ElementowaTablica > dist;
- int main()
- {
- #ifndef DEBUG
- ios_base::sync_with_stdio(false); cin.tie(0);
- #endif // DEBUG
- int w, h;
- cin >> h >> w;
- string startDir;
- cin >> startDir;
- plansz.resize(2 * w + 1, V<char>(2 * h + 1));
- dist.resize(2 * w + 1, V< wcaleNie4ElementowaTablica >(2 * h + 1));
- for(int x = 1; x < 2 * w + 1; x += 2)
- for(int y = 1; y < 2 * h + 1; y += 2)
- dist[x][y][0] = dist[x][y][1] = dist[x][y][2] = dist[x][y][3] = INF;
- xy start, end;
- for(int y = 2 * h; y >= 0; y--)
- FOR(x, 0, 2 * w + 1)
- {
- cin >> plansz[x][y];
- if(plansz[x][y] == 'S')
- start = {x, y};
- if(plansz[x][y] == 'R')
- end = {x, y};
- }
- if(startDir == "DOL")start.dir = 0;
- if(startDir == "PRAWO")start.dir = 1;
- if(startDir == "GORA")start.dir = 2;
- if(startDir == "LEWO")start.dir = 3;
- LOG(plansz)
- LN(start)
- LN(end)
- set < P<int, xy> > kolej = {{0, start}};
- dist[start][start.dir] = 0;
- V<int> dirs = {0, 3, 1, 2};
- V<xy> deltas;
- while(!kolej.empty())
- {
- xy v = kolej.begin()->S;
- kolej.erase(kolej.begin());
- #define getDelta(d) ((d) == 0 ? xy(0, -1) : (d) == 1 ? xy(1, 0) : (d) == 2 ? xy(0, 1) : xy(-1, 0))
- int goCost = 0;
- for(auto &d : dirs)
- {
- char curDir = (v.dir + d > 3 ? v.dir + d - 4 : v.dir + d);
- xy curDelt = getDelta(curDir);
- xy wall = v + curDelt;
- if(plansz[wall] == '-' || plansz[wall] == '|')
- continue;
- xy nxt = wall + curDelt;
- nxt.dir = curDir;
- if(dist[v][v.dir] + goCost < dist[nxt][curDir])
- {
- kolej.erase({dist[nxt][curDir], nxt});
- dist[nxt][curDir] = dist[v][v.dir] + goCost;
- kolej.insert({dist[nxt][curDir], nxt});
- }
- goCost = 1;
- }
- }
- int res = mini(dist[end][0], dist[end][1], dist[end][2], dist[end][3]);
- cout << (res == INF ? -1 : res) << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement