Advertisement
Guest User

Untitled

a guest
Nov 29th, 2015
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.04 KB | None | 0 0
  1. namespace Labyrinth
  2. {
  3. using System;
  4. using System.Collections.Generic;
  5. using System.Linq;
  6.  
  7. public class Program
  8. {
  9. private static List<char[,]> labirynth;
  10. private static List<bool[,]> visited;
  11. private static int minCount = int.MaxValue;
  12.  
  13. public static void Main()
  14. {
  15. var startPosition = Console.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
  16. .Select(int.Parse)
  17. .ToArray();
  18.  
  19. var position = new Position
  20. {
  21. Row = startPosition[1],
  22. Col = startPosition[2],
  23. Floor = startPosition[0],
  24. Path = 0
  25. };
  26.  
  27. var matrixSize = Console.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
  28. .Select(int.Parse)
  29. .ToArray();
  30. var floors = matrixSize[0];
  31. labirynth = new List<char[,]>(floors);
  32. visited = new List<bool[,]>(floors);
  33.  
  34. for (int m = 0; m < matrixSize[0]; m++)
  35. {
  36. var matrix = new char[matrixSize[1], matrixSize[2]];
  37. visited.Add(new bool[matrixSize[1], matrixSize[2]]);
  38.  
  39. for (int row = 0; row < matrix.GetLength(0); row++)
  40. {
  41. var line = Console.ReadLine();
  42. for (int col = 0; col < matrix.GetLength(1); col++)
  43. {
  44. matrix[row, col] = line[col];
  45. }
  46. }
  47.  
  48. labirynth.Add(matrix);
  49.  
  50. }
  51.  
  52. Bfs(position);
  53. Console.WriteLine(minCount);
  54. }
  55.  
  56. private static void Bfs(Position position)
  57. {
  58. var queue = new Queue<Position>();
  59. queue.Enqueue(position);
  60.  
  61. while (queue.Count > 0)
  62. {
  63. var currentPosition = queue.Dequeue();
  64.  
  65. if (currentPosition.Floor < 0 || currentPosition.Floor >= labirynth.Count)
  66. {
  67. if (currentPosition.Path < minCount)
  68. {
  69. minCount = currentPosition.Path;
  70. }
  71.  
  72. continue;
  73. }
  74.  
  75. var used = visited[currentPosition.Floor];
  76. var isUsedStep = used[currentPosition.Row, currentPosition.Col];
  77.  
  78. if (isUsedStep)
  79. {
  80. continue;
  81. }
  82.  
  83. var floor = labirynth[currentPosition.Floor];
  84. var step = floor[currentPosition.Row, currentPosition.Col];
  85.  
  86. if (step == '#')
  87. {
  88. continue;
  89. }
  90.  
  91. used[currentPosition.Row, currentPosition.Col] = true;
  92.  
  93. if (step == 'U')
  94. {
  95. queue.Enqueue(new Position
  96. {
  97. Row = currentPosition.Row,
  98. Col = currentPosition.Col,
  99. Floor = currentPosition.Floor + 1,
  100. Path = currentPosition.Path + 1
  101. });
  102. }
  103. else if (step == 'D')
  104. {
  105. queue.Enqueue(new Position
  106. {
  107. Row = currentPosition.Row,
  108. Col = currentPosition.Col,
  109. Floor = currentPosition.Floor - 1,
  110. Path = currentPosition.Path + 1
  111. });
  112. }
  113. else
  114. {
  115. if (currentPosition.Row + 1 < floor.GetLength(0) && !used[currentPosition.Row + 1, currentPosition.Col] &&
  116. labirynth[currentPosition.Floor][currentPosition.Row + 1, currentPosition.Col] != '#')
  117. {
  118. queue.Enqueue(new Position
  119. {
  120. Row = currentPosition.Row + 1,
  121. Col = currentPosition.Col,
  122. Floor = currentPosition.Floor,
  123. Path = currentPosition.Path + 1
  124. });
  125. }
  126.  
  127. if (currentPosition.Row - 1 >= 0 && !used[currentPosition.Row - 1, currentPosition.Col] &&
  128. labirynth[currentPosition.Floor][currentPosition.Row - 1, currentPosition.Col] != '#')
  129. {
  130. queue.Enqueue(new Position
  131. {
  132. Row = currentPosition.Row - 1,
  133. Col = currentPosition.Col,
  134. Floor = currentPosition.Floor,
  135. Path = currentPosition.Path + 1
  136. });
  137. }
  138.  
  139. if (currentPosition.Col + 1 < floor.GetLength(1) && !used[currentPosition.Row, currentPosition.Col + 1] &&
  140. labirynth[currentPosition.Floor][currentPosition.Row, currentPosition.Col + 1] != '#')
  141. {
  142. queue.Enqueue(new Position
  143. {
  144. Row = currentPosition.Row,
  145. Col = currentPosition.Col + 1,
  146. Floor = currentPosition.Floor,
  147. Path = currentPosition.Path + 1
  148. });
  149. }
  150.  
  151. if (currentPosition.Col - 1 >= 0 && !used[currentPosition.Row, currentPosition.Col - 1] &&
  152. labirynth[currentPosition.Floor][currentPosition.Row, currentPosition.Col - 1] != '#')
  153. {
  154. queue.Enqueue(new Position
  155. {
  156. Row = currentPosition.Row,
  157. Col = currentPosition.Col - 1,
  158. Floor = currentPosition.Floor,
  159. Path = currentPosition.Path + 1
  160. });
  161. }
  162. }
  163. }
  164. }
  165.  
  166. private static void WalkMatrixRecursive(Position position, int steps)
  167. {
  168. if (position.Floor < 0 || position.Floor >= labirynth.Count)
  169. {
  170. if (steps < minCount)
  171. {
  172. minCount = steps;
  173. }
  174.  
  175. return;
  176. }
  177.  
  178. if (position.Row < 0 || position.Row >= labirynth[0].GetLength(0))
  179. {
  180. return;
  181. }
  182.  
  183. if (position.Col < 0 || position.Col >= labirynth[0].GetLength(1))
  184. {
  185. return;
  186. }
  187.  
  188.  
  189. var floor = labirynth[position.Floor];
  190. var step = floor[position.Row, position.Col];
  191.  
  192. var used = visited[position.Floor];
  193. var isUsedStep = used[position.Row, position.Col];
  194.  
  195. if (step == '#')
  196. {
  197. return;
  198. }
  199.  
  200. if (isUsedStep)
  201. {
  202. return;
  203. }
  204.  
  205. if (step == 'U')
  206. {
  207. used[position.Row, position.Col] = true;
  208. steps++;
  209. position.Floor++;
  210. WalkMatrixRecursive(position, steps);
  211. position.Floor--;
  212. steps--;
  213. used[position.Row, position.Col] = false;
  214. }
  215. else if (step == 'D')
  216. {
  217. used[position.Row, position.Col] = true;
  218. steps++;
  219. position.Floor--;
  220. WalkMatrixRecursive(position, steps);
  221. position.Floor++;
  222. steps--;
  223. used[position.Row, position.Col] = false;
  224. }
  225. else
  226. {
  227. if (position.Row + 1 < floor.GetLength(0) && !used[position.Row + 1, position.Col] && step != '#')
  228. {
  229. used[position.Row, position.Col] = true;
  230. steps++;
  231. position.Row++;
  232. WalkMatrixRecursive(position, steps);
  233. position.Row--;
  234. steps--;
  235. used[position.Row, position.Col] = false;
  236. }
  237.  
  238. if (position.Row - 1 >= 0 && !used[position.Row - 1, position.Col] && step != '#')
  239. {
  240. used[position.Row, position.Col] = true;
  241. steps++;
  242. position.Row--;
  243. WalkMatrixRecursive(position, steps);
  244. position.Row++;
  245. steps--;
  246. used[position.Row, position.Col] = false;
  247. }
  248.  
  249. if (position.Col + 1 < floor.GetLength(1) && !used[position.Row, position.Col + 1] && step != '#')
  250. {
  251. used[position.Row, position.Col] = true;
  252. steps++;
  253. position.Col++;
  254. WalkMatrixRecursive(position, steps);
  255. position.Col--;
  256. steps--;
  257. used[position.Row, position.Col] = false;
  258. }
  259.  
  260. if (position.Col - 1 >= 0 && !used[position.Row, position.Col - 1] && step != '#')
  261. {
  262. used[position.Row, position.Col] = true;
  263. steps++;
  264. position.Col--;
  265. WalkMatrixRecursive(position, steps);
  266. position.Col++;
  267. steps--;
  268. used[position.Row, position.Col] = false;
  269. }
  270. }
  271. }
  272. }
  273.  
  274. public class Position
  275. {
  276. public int Row { get; set; }
  277.  
  278. public int Col { get; set; }
  279.  
  280. public int Floor { get; set; }
  281.  
  282. public int Path { get; set; }
  283. }
  284. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement