API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 20th, 2020
110
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.06 KB | None | 0 0
raw download clone embed print report
  1. #include <vector>
  2. #include <iostream>
  3. #include <queue>
  4. #include <string>
  5. #include <map>
  6.  
  7. using namespace std;
  8.  
  9.  
  10. int dist[9][9][9][9];
  11. bool marked[9][9][9][9];
  12. pair<pair<int, int>, pair<int, int>> back[9][9][9][9];
  13.  
  14. int main() {
  15. string b1, b2;
  16. string e1, e2;
  17. cin >> b1 >> b2 >> e1 >> e2;
  18. pair<int, int> s1 = { b1[0] - 'a' + 1, b1[1] - '0' };
  19. pair<int, int> s2 = { b2[0] - 'a' + 1, b2[1] - '0' };
  20. pair<int, int> s3 = { e1[0] - 'a' + 1, e1[1] - '0' };
  21. pair<int, int> s4 = { e2[0] - 'a' + 1, e2[1] - '0' };
  22. pair<pair<int, int>, pair<int, int>> start = { s1, s2 };
  23. pair<pair<int, int>, pair<int, int>> end = { s3, s4 };
  24. queue<pair<pair<int, int>, pair<int, int>>> queue;
  25. queue.push(start);
  26. marked[start.first.first][start.first.second][start.second.first][start.second.second] = 1;
  27. back[start.first.first][start.first.second][start.second.first][start.second.second] = { {- 1, - 1}, {- 1, -1} } ;
  28. while (!queue.empty()) {
  29. //
  30. pair<pair<int, int>, pair<int, int>> v = queue.front();
  31. if (v == end) {
  32. break;
  33. }
  34. if (v.first.first - 1 > 0 and v.first.second + 2 < 9 and v.second.first != (v.first.first - 1) and v.second.second != (v.first.second + 2)) {
  35. if (marked[v.first.first - 1][ v.first.second + 2][v.second.first][v.second.second] == 0) {
  36. marked[v.first.first - 1][v.first.second + 2][v.second.first][v.second.second] = 1;
  37. dist[v.first.first - 1][v.first.second + 2][v.second.first][v.second.second] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  38. back[v.first.first - 1][v.first.second + 2][v.second.first][v.second.second] = v;
  39. queue.push({ {v.first.first - 1, v.first.second + 2}, v.second });
  40. }
  41. }
  42. if (v.first.first + 1 < 9 and v.first.second + 2 < 9 and v.second.first != (v.first.first + 1) and v.second.second != (v.first.second + 2)) {
  43. if (marked[v.first.first + 1][v.first.second + 2][v.second.first][v.second.second] == 0) {
  44. marked[v.first.first + 1][v.first.second + 2][v.second.first][v.second.second] = 1;
  45. dist[v.first.first + 1][v.first.second + 2][v.second.first][v.second.second] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  46. back[v.first.first + 1][v.first.second + 2][v.second.first][v.second.second] = v;
  47. queue.push({ {v.first.first + 1, v.first.second + 2}, v.second });
  48. }
  49. }
  50. if (v.first.first - 1 > 0 and v.first.second - 2 > 0 and v.second.first != (v.first.first - 1) and v.second.second != (v.first.second - 2)) {
  51. if (marked[v.first.first - 1][v.first.second - 2][v.second.first][v.second.second] == 0) {
  52. marked[v.first.first - 1][v.first.second - 2][v.second.first][v.second.second] = 1;
  53. dist[v.first.first - 1][v.first.second - 2][v.second.first][v.second.second] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  54. back[v.first.first - 1][v.first.second - 2][v.second.first][v.second.second] = v;
  55. queue.push({ {v.first.first - 1, v.first.second - 2}, v.second });
  56. }
  57. }
  58. if (v.first.first + 1 < 9 and v.first.second - 2 > 0 and v.second.first != (v.first.first + 1) and (v.second.second != v.first.second - 2)) {
  59. if (marked[v.first.first + 1][v.first.second - 2][v.second.first][v.second.second] == 0) {
  60. marked[v.first.first + 1][v.first.second - 2][v.second.first][v.second.second] = 1;
  61. dist[v.first.first + 1][v.first.second - 2][v.second.first][v.second.second] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  62. back[v.first.first + 1][v.first.second - 2][v.second.first][v.second.second] = v;
  63. queue.push({ {v.first.first + 1, v.first.second - 2}, v.second });
  64. }
  65. }
  66. //
  67.  
  68. if (v.first.first + 2 < 9 and v.first.second + 1 < 9 and v.second.first != (v.first.first + 2) and v.second.second != (v.first.second + 1)) {
  69. if (marked[v.first.first + 2][v.first.second + 1][v.second.first][v.second.second] == 0) {
  70. marked[v.first.first + 2][v.first.second + 1][v.second.first][v.second.second] = 1;
  71. dist[v.first.first + 2][v.first.second + 1][v.second.first][v.second.second] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  72. back[v.first.first + 2][v.first.second + 1][v.second.first][v.second.second] = v;
  73. queue.push({ {v.first.first + 2, v.first.second + 1}, v.second });
  74. }
  75. }
  76. if (v.first.first + 2 < 9 and v.first.second - 1 > 0 and v.second.first != (v.first.first + 2) and v.second.second != (v.first.second - 1)) {
  77. if (marked[v.first.first + 2][v.first.second - 1][v.second.first][v.second.second] == 0) {
  78. marked[v.first.first + 2][v.first.second - 1][v.second.first][v.second.second] = 1;
  79. dist[v.first.first + 2][v.first.second - 1][v.second.first][v.second.second] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  80. back[v.first.first + 2][v.first.second - 1][v.second.first][v.second.second] = v;
  81. queue.push({ {v.first.first + 2, v.first.second - 1}, v.second });
  82. }
  83. }
  84. if (v.first.first - 2 > 0 and v.first.second + 1 < 9 and v.second.first != (v.first.first - 2) and v.second.second != (v.first.second + 1)) {
  85. if (marked[v.first.first - 2][v.first.second + 1][v.second.first][v.second.second] == 0) {
  86. marked[v.first.first - 2][v.first.second + 1][v.second.first][v.second.second] = 1;
  87. dist[v.first.first - 2][v.first.second + 1][v.second.first][v.second.second] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  88. back[v.first.first - 2][v.first.second + 1][v.second.first][v.second.second] = v;
  89. queue.push({ {v.first.first - 2, v.first.second + 1}, v.second });
  90. }
  91. }
  92. if (v.first.first - 2 > 0 and v.first.second - 1 > 0 and (v.second.first != v.first.first - 2) and v.second.second != (v.first.second - 1)) {
  93. if (marked[v.first.first - 2][v.first.second - 1][v.second.first][v.second.second] == 0) {
  94. marked[v.first.first - 2][v.first.second - 1][v.second.first][v.second.second] = 1;
  95. dist[v.first.first - 2][v.first.second - 1][v.second.first][v.second.second] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  96. back[v.first.first - 2][v.first.second - 1][v.second.first][v.second.second] = v;
  97. queue.push({ {v.first.first - 2, v.first.second - 1}, v.second });
  98. }
  99. }
  100. /// SECOND
  101. if (v.second.first - 1 > 0 and v.second.second + 2 < 9 and v.first.first != (v.second.first - 1) and v.first.second != (v.second.second + 2)) {
  102. if (marked[v.first.first][v.first.second][v.second.first - 1][v.second.second + 2] == 0) {
  103. marked[v.first.first][v.first.second][v.second.first - 1][v.second.second + 2] = 1;
  104. dist[v.first.first][v.first.second][v.second.first - 1][v.second.second + 2] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  105. back[v.first.first][v.first.second][v.second.first - 1][v.second.second + 2] = v;
  106. queue.push({ v.first ,{v.second.first - 1, v.second.second + 2} });
  107. }
  108. }
  109. if (v.second.first + 1 < 9 and v.second.second + 2 < 9 and v.first.first != (v.second.first + 1) and v.first.second != (v.second.second + 2)) {
  110. if (marked[v.first.first][v.first.second][v.second.first + 1][v.second.second + 2] == 0) {
  111. marked[v.first.first][v.first.second][v.second.first + 1][v.second.second + 2] = 1;
  112. dist[v.first.first][v.first.second][v.second.first + 1][v.second.second + 2] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  113. back[v.first.first][v.first.second][v.second.first + 1][v.second.second + 2] = v;
  114. queue.push({ v.first ,{v.second.first + 1, v.second.second + 2} });
  115. }
  116. }
  117. if (v.second.first - 1 > 0 and v.second.second - 2 > 0 and v.first.first != (v.second.first - 1) and v.first.second != (v.second.second - 2)) {
  118. if (marked[v.first.first][v.first.second][v.second.first - 1][v.second.second - 2] == 0) {
  119. marked[v.first.first][v.first.second][v.second.first - 1][v.second.second - 2] = 1;
  120. dist[v.first.first][v.first.second][v.second.first - 1][v.second.second - 2] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  121. back[v.first.first][v.first.second][v.second.first - 1][v.second.second - 2] = v;
  122. queue.push({ v.first ,{v.second.first - 1, v.second.second - 2} });
  123. }
  124. }
  125. if (v.second.first + 1 < 9 and v.second.second - 2 > 0 and v.first.first != (v.second.first + 1) and v.first.second != (v.second.second - 2)) {
  126. if (marked[v.first.first][v.first.second][v.second.first + 1][v.second.second - 2] == 0) {
  127. marked[v.first.first][v.first.second][v.second.first + 1][v.second.second - 2] = 1;
  128. dist[v.first.first][v.first.second][v.second.first + 1][v.second.second - 2] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  129. back[v.first.first][v.first.second][v.second.first + 1][v.second.second - 2] = v;
  130. queue.push({ v.first ,{v.second.first + 1, v.second.second - 2} });
  131. }
  132. }
  133. //
  134.  
  135. if (v.second.first + 2 < 9 and v.second.second + 1 < 9 and v.first.first != (v.second.first + 2) and v.first.second != (v.second.second + 1)) {
  136. if (marked[v.first.first][v.first.second][v.second.first + 2][v.second.second + 1] == 0) {
  137. marked[v.first.first][v.first.second][v.second.first + 2][v.second.second + 1] = 1;
  138. dist[v.first.first][v.first.second][v.second.first + 2][v.second.second + 1] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  139. back[v.first.first][v.first.second][v.second.first + 2][v.second.second + 1] = v;
  140. queue.push({ v.first ,{v.second.first + 2, v.second.second + 1} });
  141. }
  142. }
  143. if (v.second.first + 2 < 9 and v.second.second - 1 > 0 and (v.second.first + 2) != (v.first.first) and (v.second.second - 1) != v.first.second) {
  144. if (marked[v.first.first][v.first.second][v.second.first + 2][v.second.second - 1] == 0) {
  145. marked[v.first.first][v.first.second][v.second.first + 2][v.second.second - 1] = 1;
  146. dist[v.first.first][v.first.second][v.second.first + 2][v.second.second - 1] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  147. back[v.first.first][v.first.second][v.second.first + 2][v.second.second - 1] = v;
  148. queue.push({ v.first ,{v.second.first + 2, v.second.second - 1} });
  149. }
  150. }
  151. if (v.second.first - 2 > 0 and v.second.second + 1 < 9 and (v.second.first - 2) != (v.first.first) and (v.second.second + 1) != v.first.second) {
  152. if (marked[v.first.first][v.first.second][v.second.first - 2][v.second.second + 1] == 0) {
  153. marked[v.first.first][v.first.second][v.second.first - 2][v.second.second + 1] = 1;
  154. dist[v.first.first][v.first.second][v.second.first - 2][v.second.second + 1] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  155. back[v.first.first][v.first.second][v.second.first - 2][v.second.second + 1] = v;
  156. queue.push({ v.first ,{v.second.first - 2, v.second.second + 1} });
  157. }
  158. }
  159. if (v.second.first - 2 > 0 and v.second.second - 1 > 0 and (v.second.first - 2) != (v.first.first) and (v.second.second - 1) != v.first.second) {
  160. if (marked[v.first.first][v.first.second][v.second.first - 2][v.second.second - 1] == 0) {
  161. marked[v.first.first][v.first.second][v.second.first - 2][v.second.second - 1] = 1;
  162. dist[v.first.first][v.first.second][v.second.first - 2][v.second.second - 1] = dist[v.first.first][v.first.second][v.second.first][v.second.second] + 1;
  163. back[v.first.first][v.first.second][v.second.first - 2][v.second.second - 1] = v;
  164. queue.push({ v.first ,{v.second.first - 2, v.second.second - 1} });
  165. }
  166. }
  167. queue.pop();
  168. }
  169. pair<pair<int, int>, pair<int, int>> x = end;
  170. vector<pair<int, pair<char, int>>> ans;
  171. for (int i = 0; i < dist[end.first.first][end.first.second][end.second.first][end.second.second]; i++) {
  172. pair<pair<int, int>, pair<int, int>> y = back[x.first.first][x.first.second][x.second.first][x.second.second];
  173. if (y.first != x.first) {
  174. char symb = 'a' + y.first.first;
  175. ans.push_back({ 1, {x.first.first + 'a' - 1, x.first.second} });
  176. }
  177. else {
  178. ans.push_back({ 2, {x.second.first + 'a' - 1, x.second.second} });
  179. }
  180. x = y;
  181. }
  182. for (int i = ans.size() - 1; i >= 0; i--) {
  183. cout << ans[i].first << ' ' << ans[i].second.first << ans[i].second.second << '\n';
  184. }
  185. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!