Advertisement
Guest User

Untitled

a guest
Aug 25th, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.11 KB | None | 0 0
  1. #include<iostream>
  2. #include<fstream>
  3. #include<string>
  4. #include<vector>
  5. #include<utility>
  6. #include<algorithm>
  7. #include<climits>
  8. #include<set>
  9. #include<map>
  10. #include<cmath>
  11. #include<iomanip>
  12. #include<iterator>
  13. #include<queue>
  14. #include<stack>
  15. #include<cctype>
  16. #include<deque>
  17. #include <unordered_map>
  18. #include <unordered_set>
  19. #include <bitset>
  20.  
  21. //by Skeef79
  22.  
  23. //НЕ ИСПОЛЬЗУЙ endl, есть свой en!!
  24. //Иногда нужно не просто придумывать решение, а метматически расписать систему уравнений
  25. //для задач с cin/cout в большом кол-ве - gnu , иначе вижуалки. А ваще пробуй два если TL
  26.  
  27. //для интерактивок - cout<<flush
  28. // cin.tie и sync_with_stdio убирать для интерактивок
  29.  
  30. typedef long long ll;
  31. typedef long double ld;
  32.  
  33. #pragma warning(disable : 4996)
  34. #pragma comment(linker, "/STACK:16777216")
  35. #define pb push_back
  36. #define en '\n'
  37. #define for0(i,n) for(int i = 0;i<n;i++)
  38. #define all(x) (x).begin(),(x).end()
  39. #define allr(x) (x).rbegin(),(x).rend()
  40. #define vec vector
  41.  
  42. using namespace std;
  43.  
  44. const int INF = 1000000000 + 1233;
  45. const ll LINF = 1000000000000000000 + 1233;
  46.  
  47. template<typename T> void print(vector<T>& a)
  48. {
  49. for (int i = 0; i < a.size(); i++)
  50. cout << a[i] << ' ';
  51. }
  52.  
  53. template <typename T> void Input(vector<T>& a)
  54. {
  55. for (int i = 0; i < a.size(); i++)
  56. cin >> a[i];
  57. }
  58.  
  59. struct pt {
  60. ll x, y;
  61. };
  62.  
  63. bool cmp(pt a, pt b) {
  64. return a.x < b.x || a.x == b.x && a.y < b.y;
  65. }
  66.  
  67. bool cw(pt a, pt b, pt c) {
  68. return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
  69. }
  70.  
  71. bool ccw(pt a, pt b, pt c) {
  72. return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
  73. }
  74.  
  75. void convex_hull(vector<pt>& a) {
  76. if (a.size() == 1) return;
  77. sort(a.begin(), a.end(), &cmp);
  78. pt p1 = a[0], p2 = a.back();
  79. vector<pt> up, down;
  80. up.push_back(p1);
  81. down.push_back(p1);
  82. for (size_t i = 1; i < a.size(); ++i) {
  83. if (i == a.size() - 1 || cw(p1, a[i], p2)) {
  84. while (up.size() >= 2 && !cw(up[up.size() - 2], up[up.size() - 1], a[i]))
  85. up.pop_back();
  86. up.push_back(a[i]);
  87. }
  88. if (i == a.size() - 1 || ccw(p1, a[i], p2)) {
  89. while (down.size() >= 2 && !ccw(down[down.size() - 2], down[down.size() - 1], a[i]))
  90. down.pop_back();
  91. down.push_back(a[i]);
  92. }
  93. }
  94. a.clear();
  95. for (size_t i = 0; i < up.size(); ++i)
  96. a.push_back(up[i]);
  97. for (size_t i = down.size() - 2; i > 0; --i)
  98. a.push_back(down[i]);
  99. }
  100.  
  101. struct aaa {
  102. int i1, i2, j1, j2;
  103. aaa(int i1, int j1, int i2, int j2) {
  104. this->i1 = i1;
  105. this->i2 = i2;
  106. this->j1 = j1;
  107. this->j2 = j2;
  108. }
  109. };
  110.  
  111. int n, m;
  112.  
  113. bool check(int x, int y, vec<vec<char>> &g) {
  114. if (x < 0 || y < 0 || x >= n || y >= m || g[x][y] == '#')
  115. return false;
  116. return true;
  117. }
  118.  
  119. vec<int> dx = { 1, -1, 0, 0 };
  120. vec<int> dy = { 0, 0, 1, -1 };
  121.  
  122.  
  123. int main()
  124. {
  125. //ios::sync_with_stdio(false);
  126. //cin.tie(0);
  127. //cout.tie(0);
  128. #ifdef _DEBUG
  129. freopen("input.txt", "r", stdin);
  130. #endif
  131. //freopen("shield.in", "r", stdin);
  132. //freopen("shield.out", "w", stdout);
  133. cin >> n >> m;
  134. int xi, xj;
  135. vec<vec<char>> g(n, vec<char>(m));
  136. for0(i, n) {
  137. for0(j, m) {
  138. cin >> g[i][j];
  139. if (g[i][j] == 'X') {
  140. xi = i;
  141. xj = j;
  142. }
  143. }
  144. }
  145. vec < vec < vec < vec <ll>>>> d(n, vec<vec<vec<ll>>>(m, vec<vec<ll>>(n, vec<ll>(m, - 1))));
  146. queue<aaa> q;
  147. q.push(aaa(0, 0, xi, xj));
  148. d[0][0][xi][xj] = 0;
  149. while (!q.empty()) {
  150. aaa v = q.front();
  151. q.pop();
  152. for (int i = 0; i < 4; i++) {
  153. int newx = v.i1 + dx[i];
  154. int newy = v.j1 + dy[i];
  155. if (!check(newx, newy, g))
  156. continue;
  157. int newx2 = v.i2;
  158. int newy2 = v.j2;
  159. if (g[newx][newy] == 'X') {
  160. newx2 = v.i1;
  161. newy2 = v.j1;
  162. }
  163. if (d[newx][newy][newx2][newy2] != -1) {
  164. continue;
  165. }
  166. d[newx][newy][newx2][newy2] = d[v.i1][v.j1][v.i2][v.j2] + 1;
  167. cout << newx2 << " " << newy2 << en;
  168. if (newx2 == 0 && newy2 == 0) {
  169. cout << d[newx][newy][newx2][newy2];
  170. return 0;
  171. }
  172. q.push(aaa(newx, newy, newx2, newy2));
  173. }
  174. }
  175.  
  176. cout << "Impossible";
  177. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement