Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.77 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <limits.h>
  5. #include <math.h>
  6. #include <string>
  7.  
  8. using namespace std;
  9.  
  10. class Point2D
  11. {
  12. public:
  13.  
  14. int r;
  15. int c;
  16. Point2D()
  17. {
  18.  
  19. }
  20. Point2D(const Point2D &input)
  21. {
  22. r = input.r;
  23. c = input.c;
  24. }
  25. Point2D(int y, int x)
  26. {
  27. r = y;
  28. c = x;
  29. }
  30.  
  31. string content()
  32. {
  33. return "(" + to_string(r) + ", " + to_string(c) + ")";
  34. }
  35. };
  36.  
  37. class Adj
  38. {
  39. public:
  40. Point2D root;
  41. vector<Point2D> childs;
  42.  
  43. string content()
  44. {
  45. string str;
  46. str = root.content() + ": ";
  47. for (int i = 0; i < childs.size(); i++)
  48. {
  49. str = str + childs[i].content() + " -> ";
  50. }
  51.  
  52. return str;
  53. }
  54. };
  55.  
  56.  
  57. vector<vector<int>> getMaze(Point2D maze_size)
  58. {
  59. vector<vector<int>> maze;
  60.  
  61. char temp;
  62. for (int r = 0; r < maze_size.r; r++)
  63. {
  64. vector<int> row;
  65. for (int c = 0; c < maze_size.c; c++)
  66. {
  67. cin >> temp;
  68. row.push_back(atoi(&temp));
  69. }
  70. maze.push_back(row);
  71. }
  72.  
  73. return maze;
  74. }
  75.  
  76. Point2D getStartPoint(vector<vector<int>> &maze)
  77. {
  78. for (int r = 0; r < maze.size(); r++)
  79. {
  80. for (int c = 0; c < maze.size(); c++)
  81. {
  82. if (maze[r][c] == 2)
  83. {
  84. return Point2D(r, c);
  85. }
  86. }
  87. }
  88. }
  89.  
  90. Point2D getEndPoint(vector<vector<int>> &maze)
  91. {
  92. for (int r = 0; r < maze.size(); r++)
  93. {
  94. for (int c = 0; c < maze.size(); c++)
  95. {
  96. if (maze[r][c] == 3)
  97. {
  98. return Point2D(r, c);
  99. }
  100. }
  101. }
  102. }
  103.  
  104. bool isWall(vector<vector<int>> &maze, Point2D target)
  105. {
  106. //check is out of maze
  107. if (target.r < 0 || target.c < 0)
  108. {
  109. return true;
  110. }
  111. if (target.r >= maze.size() || target.c >= maze[0].size())
  112. {
  113. return true;
  114. }
  115.  
  116. //check is wall
  117. if (maze[target.r][target.c] == 1)
  118. {
  119. return true;
  120. }
  121.  
  122. return false;
  123. }
  124.  
  125. bool isExist(vector<Adj> list, Point2D target)
  126. {
  127. for (int i = 0; i < list.size(); i++)
  128. {
  129. if (list[i].root.c == target.c && list[i].root.r == target.r)
  130. {
  131. return true;
  132. }
  133. }
  134. return false;
  135. }
  136.  
  137. vector<Point2D> getChilds(vector<vector<int>> &maze, Point2D target)
  138. {
  139. vector<Point2D> output;
  140. Point2D up(target.r-1, target.c);
  141. Point2D down(target.r+1, target.c);
  142. Point2D left(target.r, target.c-1);
  143. Point2D right(target.r, target.c+1);
  144.  
  145. if (!isWall(maze, up))
  146. {
  147. output.push_back(up);
  148. }
  149. if (!isWall(maze, down))
  150. {
  151. output.push_back(down);
  152. }
  153. if (!isWall(maze, left))
  154. {
  155. output.push_back(left);
  156. }
  157. if (!isWall(maze, right))
  158. {
  159. output.push_back(right);
  160. }
  161.  
  162. return output;
  163. }
  164.  
  165.  
  166. bool goMaze(vector<vector<int>> &maze, Point2D point_start, Point2D point_end)
  167. {
  168. /*for (int r = 0; r < maze.size(); r++)
  169. {
  170. for (int c = 0; c < maze.size(); c++)
  171. {
  172. cout << maze[r][c] << ", ";
  173. }
  174. cout << endl;
  175. }*/
  176.  
  177.  
  178. //cout <<"Start" << point_start.content() << endl;
  179. //cout << "End" << point_end.content() << endl;
  180.  
  181. Adj firstAdj;
  182. firstAdj.root = point_start;
  183. firstAdj.childs = getChilds(maze, firstAdj.root);
  184. //cout << "FisrtAdj: " << firstAdj.content() << endl;
  185.  
  186. vector<Adj> adjList;
  187. adjList.push_back(firstAdj);
  188.  
  189. for (int finger = 0; finger < adjList.size(); finger++)
  190. {
  191.  
  192. //cout << "Current: " << adjList[finger].content() << endl;
  193.  
  194. Adj current = adjList[finger];
  195.  
  196. if (current.root.r == point_end.r && current.root.c == point_end.c)
  197. {
  198. return true;
  199. }
  200.  
  201. for (int i = 0; i < current.childs.size(); i++)
  202. {
  203. if (!isExist(adjList, current.childs[i])) //check is already in list;
  204. {
  205. Adj newAdj;
  206. newAdj.root = current.childs[i];
  207. newAdj.childs = getChilds(maze, newAdj.root);
  208. adjList.push_back(newAdj);
  209. }
  210. }
  211.  
  212. }
  213.  
  214. return false;
  215.  
  216. }
  217.  
  218. int main()
  219. {
  220. Point2D maze_size;
  221. maze_size = Point2D(16, 16);
  222.  
  223. //cout << "Maze size: " << maze_size.content() << endl;
  224.  
  225. int temp;
  226.  
  227. while (cin >> temp)
  228. {
  229. //cout << temp << ", " << endl;
  230. vector<vector<int>> curr_maze = getMaze(maze_size);
  231. Point2D point_start = getStartPoint(curr_maze);
  232. Point2D point_end = getEndPoint(curr_maze);
  233. bool suc = goMaze(curr_maze, point_start, point_end);
  234.  
  235. cout << "#" << temp;
  236.  
  237. if (suc)
  238. {
  239. cout << " 1" << endl;
  240. }
  241. else
  242. {
  243. cout << " 0" << endl;
  244. }
  245. }
  246.  
  247. //cout << "hello world" << endl;
  248.  
  249. getchar();
  250. return 0;
  251. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement