Advertisement
Guest User

Untitled

a guest
Mar 24th, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <stdlib.h>
  5. #include <vector>
  6. #include <queue>
  7.  
  8. using namespace std;
  9.  
  10. struct vertex {
  11. int i1, j1, i2, j2, range, id;
  12. } S, to;
  13.  
  14. vector <vector<int>> A, B;
  15. vector <bool> used;
  16.  
  17. queue <vertex> q;
  18.  
  19. int N, R1, C1, R2, C2;
  20. int N2, N3, N4, range = 0;
  21.  
  22. void input() {
  23. ifstream fin("input.txt");
  24. fin >> N >> R1 >> C1 >> R2 >> C2;
  25. S.i1 = R1;
  26. S.j1 = C1;
  27. S.i2 = R2;
  28. S.j2 = C2;
  29. S.range = 0;
  30.  
  31. N2 = N*N;
  32. N3 = N2*N;
  33. N4 = N3*N;
  34.  
  35. A.resize(N);
  36. B.resize(N);
  37. int temp;
  38. for (int i = 0; i < N; i++) {
  39. A[i].reserve(N);
  40. for (int j = 0; j < N; j++) {
  41. fin >> temp;
  42. A[i].push_back(temp);
  43. }
  44. }
  45. for (int i = 0; i < N; i++) {
  46. B[i].reserve(N);
  47. for (int j = 0; j < N; j++) {
  48. fin >> temp;
  49. B[i].push_back(temp);
  50. }
  51. }
  52.  
  53. fin.close();
  54. }
  55.  
  56. void output(int x) {
  57. ofstream fout("output.txt");
  58. fout << x;
  59. fout.close();
  60. }
  61.  
  62. bool check(vector <vector<int>> &lab, int i, int j) {
  63. if (i >= 0 && j >= 0 && i < N && j < N && lab[i][j] == 0)
  64. return true;
  65. else
  66. return false;
  67. }
  68.  
  69. int identify(vertex &v) {
  70. return v.i1*N3 + v.j1*N2 + v.i2*N + v.j2;
  71. }
  72.  
  73. void step_up(vertex &v) {
  74. to = v;
  75. if (check(A, to.i1 - 1, to.j1)) {
  76. to.i1 -= 1;
  77. }
  78. if (check(B, to.i2 - 1, to.j2)) {
  79. to.i2 -= 1;
  80. }
  81. to.id = identify(to);
  82. to.range++;
  83. if (to.id == 0) {
  84. output(to.range);
  85. exit(EXIT_SUCCESS);
  86. }
  87. if (!used[to.id]) {
  88. used[to.id] = true;
  89. q.push(to);
  90. }
  91. }
  92.  
  93. void step_down(vertex &v) {
  94. to = v;
  95. if (check(A, to.i1 + 1, to.j1)) {
  96. to.i1 += 1;
  97. }
  98. if (check(B, to. i2 + 1, to.j2)) {
  99. to.i2 += 1;
  100. }
  101. to.id = identify(to);
  102. to.range++;
  103. if (to.id == 0) {
  104. output(to.range);
  105. exit(EXIT_SUCCESS);
  106. }
  107. if (!used[to.id]) {
  108. used[to.id] = true;
  109. q.push(to);
  110. }
  111. }
  112.  
  113. void step_right(vertex &v) {
  114. to = v;
  115. if (check(A, to. i1, to.j1 + 1)) {
  116. to.j1 += 1;
  117. }
  118. if (check(B, to.i2, to.j2 + 1)) {
  119. to.j2 += 1;
  120. }
  121. to.id = identify(to);
  122. to.range++;
  123. if (to.id == 0) {
  124. output(to.range);
  125. exit(EXIT_SUCCESS);
  126. }
  127. if (!used[to.id]) {
  128. used[to.id] = true;
  129. q.push(to);
  130. }
  131. }
  132.  
  133. void step_left(vertex &v) {
  134. to = v;
  135. if (check(A, to. i1, to.j1 - 1)) {
  136. to.j1 -= 1;
  137. }
  138. if (check(B, to.i2, to.j2 - 1)) {
  139. to.j2 -= 1;
  140. }
  141. to.id = identify(to);
  142. to.range++;
  143. if (to.id == 0) {
  144. output(to.range);
  145. exit(EXIT_SUCCESS);
  146. }
  147. if (!used[to.id]) {
  148. used[to.id] = true;
  149. q.push(to);
  150. }
  151. }
  152.  
  153. void bfs() {
  154. used.resize(N4);
  155. S.id = S.i1*N3 + S.j1*N2 + S.i2*N + S.j2;
  156. used[S.id] = true;
  157. q.push(S);
  158. int result = -1;
  159.  
  160. while (!q.empty()) {
  161. vertex v = q.front();
  162. q.pop();
  163.  
  164. // if (check(A, v.i1 - 1, v.j1) && check(A, v.i2 - 1, v.j2) && !used[identify(v) - N3 - N])
  165. step_up(v);
  166.  
  167. // if (check(A, v.i1 + 1, v.j1) && check(A, v.i2 + 1, v.j2) && !used[identify(v) + N3 + N])
  168. step_down(v);
  169.  
  170. // if (check(A, v.i1, v.j1 - 1) && check(A, v.i2, v.j2 - 1) && !used[identify(v) - N2 - 1])
  171. step_left(v);
  172.  
  173. // if (check(A, v.i1, v.j1 + 1) && check(A, v.i2, v.j2 + 1) && !used[identify(v) + N2 + 1])
  174. step_right(v);
  175.  
  176. }
  177.  
  178. }
  179.  
  180. int main() {
  181. input();
  182. bfs();
  183. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement