Advertisement
Guest User

YOU APPROACHING ME????

a guest
May 26th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.42 KB | None | 0 0
  1. //part one
  2.  
  3. #include <iostream>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <vector>
  7. #include <random>
  8. #include <algorithm>
  9. #define streams freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  10.  
  11. using namespace std;
  12.  
  13. struct point {
  14. int x, y;
  15. int type, f, g, h;
  16. point *parent;
  17. bool opened, closed;
  18. };
  19.  
  20. point lab[1000][1000];
  21.  
  22. int n, m;
  23. int startX, startY;
  24. int endX, endY;
  25.  
  26. bool done = false;
  27. vector <point> visited;
  28.  
  29. void getData()
  30. {
  31. cin >> n >> m;
  32. cin >> startX >> startY;
  33. cin >> endX >> endY;
  34.  
  35. for (int i = 1; i <= n; i++)
  36. for (int j = 1; j <= m; j++)
  37. {
  38. cin >> lab[i][j].type;
  39. lab[i][j].y = i;
  40. lab[i][j].x = j;
  41. }
  42. }
  43.  
  44. void setStartPos()
  45. {
  46. lab[startY][startX].g = 1;
  47. lab[startY][startX].h = endX - startX + endY - startY; //Manhattan distance
  48.  
  49. lab[startY][startX].f = lab[startY][startX].g + lab[startY][startX].h;
  50. lab[startY][startX].opened = true;
  51.  
  52. visited.push_back(lab[startY][startX]);
  53. }
  54.  
  55. void check_successor(int dy, int dx, point A)
  56. {
  57. if (A.x + dx > 0 && A.x + dx < m + 1 && A.y + dy > 0 && A.y + dy < n + 1 && lab[A.y + dy][A.x + dx].type == 0)
  58. {
  59. int cur_f = lab[A.y][A.x].g + 1 + endX - (A.x + dx) + endY - (A.y + dy);
  60.  
  61. if (lab[A.y + dy][A.x + dx].x == endX && lab[A.y + dy][A.x + dx].y == endY)
  62. done = true;
  63. else
  64. if (lab[A.y + dy][A.x + dx].opened && lab[A.y + dy][A.x + dx].f <= cur_f)
  65. return;
  66. else
  67. if (lab[A.y + dy][A.x + dx].closed && lab[A.y + dy][A.x + dx].f <= cur_f)
  68. return;
  69.  
  70. lab[A.y + dy][A.x + dx].parent = &lab[A.y][A.x];
  71. lab[A.y + dy][A.x + dx].g = lab[A.y + dy][A.x + dx].parent -> g + 1;
  72.  
  73. lab[A.y + dy][A.x + dx].h = endX - lab[A.y + dy][A.x + dx].x + endY - lab[A.y + dy][A.x + dx].y;
  74. lab[A.y + dy][A.x + dx].f = lab[A.y + dy][A.x + dx].g + lab[A.y + dy][A.x + dx].h;
  75.  
  76. lab[A.y + dy][A.x + dx].opened = true;
  77. visited.push_back(lab[A.y + dy][A.x + dx]);
  78. }
  79. }
  80.  
  81. bool comp_func(point a, point b)
  82. {
  83. if (a.f > b.f)
  84. return true;
  85. else
  86. return false;
  87. }
  88.  
  89. void print_path(point point)
  90. {
  91. if (point.parent != NULL)
  92. print_path(*point.parent);
  93.  
  94. cout << point.x << " " << point.y << endl;
  95. }
  96.  
  97. void JosephJoestar()
  98. {
  99. int sup[8] = {-1, 0, 0, 1, 1, 0, 0, -1};
  100. point tmp;
  101.  
  102. while (!visited.empty() && !done)
  103. {
  104. tmp = visited.back();
  105. visited.pop_back();
  106. lab[tmp.y][tmp.x].opened = false;
  107.  
  108. for (int i = 0; i < 8; i += 2)
  109. {
  110. if (!done)
  111. {
  112. check_successor(sup[i], sup[i + 1], tmp);
  113. }
  114. }
  115. lab[tmp.y][tmp.x].closed = true;
  116. sort(visited.begin(), visited.end(), comp_func);
  117. }
  118.  
  119. cout << lab[endY][endX].f << endl;
  120. print_path(lab[endY][endX]);
  121. }
  122.  
  123. int main()
  124. {
  125. #ifndef LOCAL
  126. streams;
  127. #endif
  128.  
  129. getData();
  130. setStartPos();
  131. JosephJoestar();
  132.  
  133. return 0;
  134. }
  135.  
  136. // part two
  137.  
  138. #include <iostream>
  139. #include <cmath>
  140. #include <iomanip>
  141. #include <vector>
  142. #include <random>
  143. #include <algorithm>
  144. #define streams freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  145.  
  146. using namespace std;
  147.  
  148. struct point {
  149. int x, y;
  150. int type, f, g, h;
  151. point *parent;
  152. bool opened, closed;
  153. };
  154.  
  155. point lab[1000][1000];
  156.  
  157. int n, m;
  158. int startX, startY;
  159. int endX, endY;
  160.  
  161. bool done = false;
  162. vector <point> visited;
  163.  
  164. void getData()
  165. {
  166. cin >> n >> m;
  167. cin >> startX >> startY;
  168. cin >> endX >> endY;
  169.  
  170. for (int i = 1; i <= n; i++)
  171. for (int j = 1; j <= m; j++)
  172. {
  173. cin >> lab[i][j].type;
  174. lab[i][j].y = i;
  175. lab[i][j].x = j;
  176. }
  177. }
  178.  
  179. void setStartPos()
  180. {
  181. lab[startY][startX].g = 1;
  182. lab[startY][startX].h = endX - startX + endY - startY;
  183.  
  184. lab[startY][startX].f = lab[startY][startX].g + lab[startY][startX].h;
  185. lab[startY][startX].opened = true;
  186.  
  187. visited.push_back(lab[startY][startX]);
  188. }
  189.  
  190. void check_successor(int dy, int dx, point A)
  191. {
  192. if (A.x + dx > 0 && A.x + dx < m + 1 && A.y + dy > 0 && A.y + dy < n + 1 && lab[A.y + dy][A.x + dx].type == 0)
  193. {
  194. int cur_f = lab[A.y][A.x].g + 1 + endX - (A.x + dx) + endY - (A.y + dy);
  195.  
  196. if (lab[A.y + dy][A.x + dx].x == endX && lab[A.y + dy][A.x + dx].y == endY)
  197. done = true;
  198. else
  199. if (lab[A.y + dy][A.x + dx].opened && lab[A.y + dy][A.x + dx].f <= cur_f)
  200. return;
  201. else
  202. if (lab[A.y + dy][A.x + dx].closed && lab[A.y + dy][A.x + dx].f <= cur_f)
  203. return;
  204.  
  205. lab[A.y + dy][A.x + dx].parent = &lab[A.y][A.x];
  206. lab[A.y + dy][A.x + dx].g = lab[A.y + dy][A.x + dx].parent -> g + 1;
  207.  
  208. lab[A.y + dy][A.x + dx].h = endX - lab[A.y + dy][A.x + dx].x + endY - lab[A.y + dy][A.x + dx].y;
  209. lab[A.y + dy][A.x + dx].f = lab[A.y + dy][A.x + dx].g + lab[A.y + dy][A.x + dx].h;
  210.  
  211. lab[A.y + dy][A.x + dx].opened = true;
  212. visited.push_back(lab[A.y + dy][A.x + dx]);
  213. }
  214. }
  215.  
  216. bool comp_func(point a, point b)
  217. {
  218. if (a.f > b.f)
  219. return true;
  220. else
  221. return false;
  222. }
  223.  
  224. void print_path(point point)
  225. {
  226. if (point.parent != NULL)
  227. print_path(*point.parent);
  228.  
  229. cout << point.x << " " << point.y << endl;
  230. }
  231.  
  232. void JosephJoestar()
  233. {
  234. int sup[8] = {-1, 0, 0, 1, 1, 0, 0, -1};
  235. point tmp;
  236.  
  237. while (!visited.empty() && !done)
  238. {
  239. tmp = visited.back();
  240. visited.pop_back();
  241. lab[tmp.y][tmp.x].opened = false;
  242.  
  243. for (int i = 0; i < 8; i += 2)
  244. {
  245. if (!done)
  246. {
  247. check_successor(sup[i], sup[i + 1], tmp);
  248. }
  249. }
  250. lab[tmp.y][tmp.x].closed = true;
  251. sort(visited.begin(), visited.end(), comp_func);
  252. }
  253.  
  254. cout << lab[endY][endX].f << endl;
  255. print_path(lab[endY][endX]);
  256. }
  257.  
  258. int main()
  259. {
  260. #ifndef LOCAL
  261. streams;
  262. #endif
  263.  
  264. getData();
  265. setStartPos();
  266. JosephJoestar();
  267.  
  268. return 0;
  269. }
  270.  
  271. // part three
  272.  
  273. #include <iostream>
  274. #include <cmath>
  275. #include <iomanip>
  276. #include <vector>
  277. #include <random>
  278. #include <algorithm>
  279. #define streams freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  280.  
  281. using namespace std;
  282.  
  283. struct point {
  284. int x, y;
  285. int type, f, g, h;
  286. point *parent;
  287. bool opened, closed;
  288. };
  289.  
  290. point lab[1000][1000];
  291.  
  292. int n, m;
  293. int startX, startY;
  294. int endX, endY;
  295.  
  296. bool done = false;
  297. vector <point> visited;
  298.  
  299. void getData()
  300. {
  301. cin >> n >> m;
  302. cin >> startX >> startY;
  303. cin >> endX >> endY;
  304.  
  305. for (int i = 1; i <= n; i++)
  306. for (int j = 1; j <= m; j++)
  307. {
  308. cin >> lab[i][j].type;
  309. lab[i][j].y = i;
  310. lab[i][j].x = j;
  311. }
  312. }
  313.  
  314. void setStartPos()
  315. {
  316. lab[startY][startX].g = 1;
  317. lab[startY][startX].h = endX - startX + endY - startY;
  318.  
  319. lab[startY][startX].f = lab[startY][startX].g + lab[startY][startX].h;
  320. lab[startY][startX].opened = true;
  321.  
  322. visited.push_back(lab[startY][startX]);
  323. }
  324.  
  325. void check_successor(int dy, int dx, point A)
  326. {
  327. if (A.x + dx > 0 && A.x + dx < m + 1 && A.y + dy > 0 && A.y + dy < n + 1 && lab[A.y + dy][A.x + dx].type == 0)
  328. {
  329. int cur_f = lab[A.y][A.x].g + 1 + endX - (A.x + dx) + endY - (A.y + dy);
  330.  
  331. if (lab[A.y + dy][A.x + dx].x == endX && lab[A.y + dy][A.x + dx].y == endY)
  332. done = true;
  333. else
  334. if (lab[A.y + dy][A.x + dx].opened && lab[A.y + dy][A.x + dx].f <= cur_f)
  335. return;
  336. else
  337. if (lab[A.y + dy][A.x + dx].closed && lab[A.y + dy][A.x + dx].f <= cur_f)
  338. return;
  339.  
  340. lab[A.y + dy][A.x + dx].parent = &lab[A.y][A.x];
  341. lab[A.y + dy][A.x + dx].g = lab[A.y + dy][A.x + dx].parent -> g + 1;
  342.  
  343. lab[A.y + dy][A.x + dx].h = endX - lab[A.y + dy][A.x + dx].x + endY - lab[A.y + dy][A.x + dx].y;
  344. lab[A.y + dy][A.x + dx].f = lab[A.y + dy][A.x + dx].g + lab[A.y + dy][A.x + dx].h;
  345.  
  346. lab[A.y + dy][A.x + dx].opened = true;
  347. visited.push_back(lab[A.y + dy][A.x + dx]);
  348. }
  349. }
  350.  
  351. bool comp_func(point a, point b)
  352. {
  353. if (a.f > b.f)
  354. return true;
  355. else
  356. return false;
  357. }
  358.  
  359. void print_path(point point)
  360. {
  361. if (point.parent != NULL)
  362. print_path(*point.parent);
  363.  
  364. cout << point.x << " " << point.y << endl;
  365. }
  366.  
  367. void JosephJoestar()
  368. {
  369. int sup[8] = {-1, 0, 0, 1, 1, 0, 0, -1};
  370. point tmp;
  371.  
  372. while (!visited.empty() && !done)
  373. {
  374. tmp = visited.back();
  375. visited.pop_back();
  376. lab[tmp.y][tmp.x].opened = false;
  377.  
  378. for (int i = 0; i < 8; i += 2)
  379. {
  380. if (!done)
  381. {
  382. check_successor(sup[i], sup[i + 1], tmp);
  383. }
  384. }
  385. lab[tmp.y][tmp.x].closed = true;
  386. sort(visited.begin(), visited.end(), comp_func);
  387. }
  388.  
  389. cout << lab[endY][endX].f << endl;
  390. print_path(lab[endY][endX]);
  391. }
  392.  
  393. int main()
  394. {
  395. #ifndef LOCAL
  396. streams;
  397. #endif
  398.  
  399. getData();
  400. setStartPos();
  401. JosephJoestar();
  402.  
  403. return 0;
  404. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement