Advertisement
Guest User

Untitled

a guest
Mar 24th, 2017
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <stdlib.h>
  5. #include <vector>
  6. #include <map>
  7. #include <queue>
  8.  
  9. using namespace std;
  10.  
  11. vector <vector<int>> A, B;
  12. int N, R1, C1, R2, C2;
  13. int N2, N3, N4;
  14. bool finish = false;
  15. struct vertex {
  16. int x1, y1, x2, y2, range, id;
  17. } S;
  18.  
  19.  
  20. void input() {
  21. ifstream fin("input1.txt");
  22. fin >> N >> R1 >> C1 >> R2 >> C2;
  23. S.x1 = R1; // строка 1
  24. S.y1 = C1; // столбец 1
  25. S.x2 = R2; // строка 2
  26. S.y2 = C2; // столбец 2
  27. S.range = 0;
  28.  
  29. N2 = N*N;
  30. N3 = N2*N;
  31. N4 = N3*N;
  32.  
  33. A.resize(N);
  34. B.resize(N);
  35. int temp;
  36. for (int i = 0; i < N; i++) {
  37. A[i].reserve(N);
  38. for (int j = 0; j < N; j++) {
  39. fin >> temp;
  40. A[i].push_back(temp);
  41. }
  42. }
  43. for (int i = 0; i < N; i++) {
  44. B[i].reserve(N);
  45. for (int j = 0; j < N; j++) {
  46. fin >> temp;
  47. B[i].push_back(temp);
  48. }
  49. }
  50.  
  51. fin.close();
  52. }
  53. int range = 0;
  54. bool f = false;
  55. vertex to;
  56. vector <bool> used;
  57. queue <vertex> q;
  58.  
  59. void step_up(vertex v) {
  60. f = false;
  61. to.x1 = to.y1 = to.x2 = to.y2 = to.id = to.range = -1;
  62. if (v.x1 - 1 >= 0) {
  63. f = true;
  64. if (A[v.x1 - 1][v.y1] == 0) {
  65. to.x1 = v.x1 - 1;
  66. to.y1 = v.y1;
  67. to.id = (v.x1 - 1)*N3 + v.y1*N2;
  68. }
  69. else {
  70. to.x1 = v.x1;
  71. to.y1 = v.y1;
  72. to.id = v.x1*N3 + v.y1*N2;
  73. }
  74. }
  75.  
  76. if (v.x2 - 1 >= 0) {
  77. f = true;
  78. if (B[v.x2 - 1][v.y2] == 0) {
  79. to.x2 = v.x2 - 1;
  80. to.y2 = v.y2;
  81. to.id += (v.x2 - 1)*N + v.y2;
  82. }
  83. else {
  84. to.x2 = v.x2;
  85. to.y2 = v.y2;
  86. to.id += v.x2*N + v.y2;
  87. }
  88. }
  89. if (to.x1 == 0 && to.y1 == 0 && to.x2 == 0 && to.y2 == 0) {
  90. finish = true;
  91. v.range = range;
  92. }
  93. if (f && !used[to.id]) {
  94. used[to.id] = true;
  95. to.range = range;
  96. q.push(to);
  97. }
  98. }
  99. void step_down(vertex v) {
  100. f = false;
  101. to.x1 = to.y1 = to.x2 = to.y2 = to.id = to.range = -1;
  102. if (v.x1 + 1 < N) {
  103. f = true;
  104. if (A[v.x1 + 1][v.y1] == 0) {
  105. to.x1 = v.x1 + 1;
  106. to.y1 = v.y1;
  107. to.id = (v.x1 + 1)*N3 + v.y1*N2;
  108. }
  109. else {
  110. to.x1 = v.x1;
  111. to.y1 = v.y1;
  112. to.id = v.x1*N3 + v.y1*N2;
  113. }
  114. }
  115.  
  116. if (v.x2 + 1 < N) {
  117. f = true;
  118. if (B[v.x2 + 1][v.y2] == 0) {
  119. to.x2 = v.x2 + 1;
  120. to.y2 = v.y2;
  121. to.id += (v.x2 + 1)*N + v.y2;
  122. }
  123. else {
  124. to.x2 = v.x2;
  125. to.y2 = v.y2;
  126. to.id += v.x2*N + v.y2;
  127. }
  128. }
  129. if (to.x1 == 0 && to.y1 == 0 && to.x2 == 0 && to.y2 == 0) {
  130. finish = true;
  131. v.range = range;
  132. }
  133.  
  134. if (f && !used[to.id]) {
  135. used[to.id] = true;
  136. to.range = range;
  137. q.push(to);
  138. }
  139. }
  140. void step_right(vertex v) {
  141. f = false;
  142. to.x1 = to.y1 = to.x2 = to.y2 = to.id = to.range = -1;
  143. if (v.y1 + 1 < N) {
  144. f = true;
  145. if (A[v.x1][v.y1 + 1] == 0) {
  146. to.x1 = v.x1;
  147. to.y1 = v.y1 + 1;
  148. to.id = v.x1*N3 + (v.y1 + 1)*N2;
  149. }
  150. else {
  151. to.x1 = v.x1;
  152. to.y1 = v.y1;
  153. to.id = v.x1*N3 + v.y1*N2;
  154. }
  155. }
  156. if (v.y2 + 1 < N) {
  157. f = true;
  158. if (B[v.x2][v.y2 + 1] == 0) {
  159. to.x2 = v.x2;
  160. to.y2 = v.y2 + 1;
  161. to.id += v.x2*N + (v.y2 + 1);
  162. }
  163. else {
  164. to.x2 = v.x2;
  165. to.y2 = v.y2;
  166. to.id += v.x2*N + v.y2;
  167. }
  168. }
  169.  
  170. if (to.x1 == 0 && to.y1 == 0 && to.x2 == 0 && to.y2 == 0) {
  171. finish = true;
  172. v.range = range;
  173. }
  174.  
  175. if (f && !used[to.id]) {
  176. used[to.id] = true;
  177. to.range = range;
  178. q.push(to);
  179. }
  180. }
  181. void step_left(vertex v) {
  182. f = false;
  183. to.x1 = to.y1 = to.x2 = to.y2 = to.id = to.range = -1;
  184. if (v.y1 - 1 >= 0) {
  185. f = true;
  186. if (A[v.x1][v.y1 - 1] == 0) {
  187. to.x1 = v.x1;
  188. to.y1 = v.y1 - 1;
  189. to.id = v.x1*N + (v.y1 - 1)*N2;
  190. }
  191. else {
  192. to.x1 = v.x1;
  193. to.y1 = v.y1;
  194. to.id = v.x1*N3 + v.y1*N2;
  195. }
  196. }
  197.  
  198. if (v.y2 - 1 >= 0) {
  199. f = true;
  200. if (B[v.x2][v.y2 - 1] == 0) {
  201. to.x2 = v.x2;
  202. to.y2 = v.y2 - 1;
  203. to.id += v.x2*N + (v.y2 - 1);
  204. }
  205. else {
  206. to.x2 = v.x2;
  207. to.y2 = v.y2;
  208. to.id += v.x2*N + v.y2;
  209. }
  210. }
  211.  
  212. if (to.x1 == 0 && to.y1 == 0 && to.x2 == 0 && to.y2 == 0) {
  213. finish = true;
  214. v.range = range;
  215. }
  216.  
  217. if (f && !used[to.id]) {
  218. used[to.id] = true;
  219. to.range = range;
  220. q.push(to);
  221. }
  222. }
  223.  
  224. int bfs() {
  225. used.resize(N4);
  226. S.id = S.x1*N3 + S.y1*N2 + S.x2*N + S.y2;
  227. used[S.id] = true;
  228. q.push(S);
  229.  
  230.  
  231. while (!q.empty()) {
  232. vertex v = q.front();
  233. q.pop();
  234.  
  235.  
  236. range++;
  237.  
  238. step_up(v);
  239. if (finish)
  240. return v.range + 1;
  241.  
  242. step_down(v);
  243. if (finish)
  244. return v.range + 1;
  245.  
  246. step_left(v);
  247. if (finish)
  248. return v.range + 1;
  249.  
  250. step_right(v);
  251. if (finish)
  252. return v.range + 1;
  253. }
  254. }
  255.  
  256. void output(int x) {
  257. ofstream fout("output.txt");
  258. fout << x;
  259. fout.close();
  260. }
  261.  
  262.  
  263. int main() {
  264. input();
  265. int result = bfs();
  266. output(result);
  267. cout << result << endl;
  268. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement