fork download
  1.  
  2. uses
  3. crt;
  4.  
  5. const
  6. MAXX = 20;
  7. MAXY = 25;
  8.  
  9. type
  10. TArr = array [0..MAXY, 0..MAXX] of integer;
  11.  
  12. TCell = record
  13. x: integer;
  14. y: integer;
  15. end;
  16.  
  17. TListCell = record
  18. x: integer;
  19. y: integer;
  20. G: integer;
  21. parent: TCell;
  22. end;
  23.  
  24. TListArr = array [1..10000] of TListCell;
  25.  
  26. TList = record
  27. arr: TListArr;
  28. len: integer;
  29. end;
  30.  
  31. var
  32. i, j, minind, ind, c: integer;
  33. start, finish: TCell;
  34. current: TListCell;
  35. field: TArr;
  36. opened, closed: TList;
  37.  
  38. procedure ShowField;
  39. var
  40. i, j: integer;
  41. begin
  42. textcolor(15);
  43. for i := 0 to MAXX do
  44. begin
  45. for j := 0 to MAXY do
  46. begin
  47. case field[j, i] of
  48. 99: textcolor(8); // непроходимая
  49. 71: textcolor(14); // проходимая
  50. 11: textcolor(10); // старт
  51. 21: textcolor(12); // финиш
  52. 15: textcolor(2); // путь
  53. 14: textcolor(5);
  54. 16: textcolor(6);
  55. end;
  56. write(field[j, i], ' ');
  57. end;
  58. writeln;
  59. end;
  60. textcolor(15);
  61. end;
  62.  
  63.  
  64.  
  65. procedure AddClosed(a: TListCell);
  66. begin
  67. closed.arr[closed.len + 1] := a;
  68. inc(closed.len);
  69. end;
  70.  
  71.  
  72. procedure AddOpened(x, y, G: integer);
  73. begin
  74. opened.arr[opened.len + 1].x := x;
  75. opened.arr[opened.len + 1].y := y;
  76. opened.arr[opened.len + 1].G := G;
  77. inc(opened.len);
  78. end;
  79.  
  80. procedure DelOpened(n: integer);
  81. var
  82. i: integer;
  83. begin
  84. AddClosed(opened.arr[n]);
  85. for i := n to opened.len - 1 do
  86. opened.arr[i] := opened.arr[i + 1];
  87. dec(opened.len);
  88. end;
  89.  
  90.  
  91. procedure SetParent(var a: TListCell; parx, pary: integer);
  92. begin
  93. a.parent.x := parx;
  94. a.parent.y := pary;
  95. end;
  96.  
  97.  
  98. function GetMin(var a: TList): integer;
  99. var
  100. i, min, mini: integer;
  101. begin
  102. min := MaxInt;
  103. mini := 0;
  104. for i := 1 to a.len do
  105. if a.arr[i].G < min then
  106. begin
  107. min := a.arr[i].G;
  108. mini := i;
  109. end;
  110.  
  111. GetMin := mini;
  112. end;
  113.  
  114.  
  115. function FindCell(a: TList; x, y: integer): integer;
  116. var
  117. i: integer;
  118. begin
  119. FindCell := 0;
  120. for i := 1 to a.len do
  121. if (a.arr[i].x = x) and (a.arr[i].y = y) then
  122. begin
  123. FindCell := i;
  124. break;
  125. end;
  126. end;
  127.  
  128.  
  129. procedure ProcessNeighbourCell(x, y: integer);
  130. begin
  131. if (field[current.x + x, current.y + y] <> 99) then // если проходима
  132. if (FindCell(closed, current.x + x, current.y + y) <= 0) then // и еще не посещена
  133. if (FindCell(opened, current.x + x, current.y + y) <= 0) then // и еще не добавлена в список
  134. begin
  135. AddOpened(current.x + x, current.y + y, current.G + 10);
  136. SetParent(opened.arr[opened.len], current.x, current.y);
  137. end
  138. else
  139. begin
  140.  
  141. end;
  142. end;
  143.  
  144.  
  145. begin
  146. randomize;
  147. for i := 0 to MAXX do
  148. for j := 0 to MAXY do
  149. field[j, i] := 99;
  150.  
  151. for i := 1 to MAXX - 1 do
  152. for j := 1 to MAXY - 1 do
  153. if random(5) mod 5 = 0 then
  154. field[j, i] := 99
  155. else field[j, i] := 71;
  156.  
  157. // координаты начальной и конечной позиций
  158. start.x := 5;
  159. start.y := 3;
  160.  
  161. finish.x := 19;
  162. finish.y := 16;
  163.  
  164. field[start.x, start.y] := 11;
  165. field[finish.x, finish.y] := 21;
  166.  
  167. ShowField;
  168.  
  169. writeln;
  170.  
  171. opened.len := 0;
  172. closed.len := 0;
  173. AddOpened(start.x, start.y, 0);
  174. SetParent(opened.arr[opened.len], -1, -1);
  175. current.x := start.x;
  176. current.y := start.y;
  177.  
  178. repeat
  179. minind := GetMin(opened);
  180. current.x := opened.arr[minind].x;
  181. current.y := opened.arr[minind].y;
  182. current.G := opened.arr[minind].G;
  183. DelOpened(minind);
  184.  
  185. ProcessNeighbourCell(1, 0); // проверить ячейку справа
  186. ProcessNeighbourCell(-1, 0); // проверить ячейку слева
  187. ProcessNeighbourCell(0, 1); // проверить ячейку сверху
  188. ProcessNeighbourCell(0, -1); // проверить ячейку снизу
  189.  
  190. if (FindCell(opened, finish.x, finish.y) > 0) then
  191. break;
  192. until opened.len = 0;
  193.  
  194. // считаем и отмечаем обратный путь
  195. c := 0;
  196. while ((current.x <> start.x) or (current.y <> start.y)) do
  197. begin
  198. field[current.x, current.y] := 15;
  199. ind := FindCell(closed, current.x, current.y);
  200. current.x := closed.arr[ind].parent.x;
  201. current.y := closed.arr[ind].parent.y;
  202. inc(c);
  203. end;
  204.  
  205. ShowField;
  206. writeln(c);
  207. readln;
  208. end.
Success #stdin #stdout 0.08s 492KB
stdin
Standard input is empty
stdout
99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 
99 71 99 71 99 71 71 71 71 71 71 71 71 71 99 71 71 71 99 71 71 71 71 71 99 99 
99 71 71 99 71 71 71 71 71 71 71 71 71 71 71 71 71 99 71 71 71 71 71 99 71 99 
99 71 99 99 99 11 99 71 71 71 99 71 71 71 71 71 71 99 99 71 71 71 71 71 71 99 
99 71 71 71 71 71 71 71 71 99 99 71 71 71 71 99 71 71 71 71 71 71 71 71 71 99 
99 71 71 71 71 71 71 71 99 71 71 71 99 71 99 71 99 71 71 71 71 71 71 99 71 99 
99 71 71 71 71 71 71 71 71 71 99 99 71 71 71 71 71 71 71 99 71 71 99 71 71 99 
99 99 71 99 71 71 71 71 71 71 71 71 71 71 71 71 71 99 71 71 71 71 99 71 71 99 
99 71 99 99 99 71 99 71 99 71 71 71 71 71 99 71 71 71 71 71 71 71 71 71 71 99 
99 71 71 71 71 71 71 71 71 71 71 99 71 71 71 71 71 71 71 71 71 71 71 71 71 99 
99 71 71 99 71 71 71 71 71 71 71 71 71 71 71 71 71 71 99 99 71 71 71 71 71 99 
99 71 71 99 71 71 99 99 71 71 71 99 71 71 99 71 99 99 71 71 99 71 71 71 71 99 
99 99 99 71 99 71 99 71 71 71 99 71 71 71 99 71 99 71 99 71 71 71 71 71 71 99 
99 71 71 71 99 99 71 99 71 99 71 71 71 71 71 71 71 71 71 71 71 71 71 71 71 99 
99 71 71 71 71 99 71 71 71 71 71 71 71 71 71 71 71 71 71 71 99 71 71 71 71 99 
99 99 71 71 71 71 71 71 71 99 71 71 71 71 71 71 71 71 71 71 71 71 71 71 71 99 
99 71 71 71 71 71 71 71 71 71 99 99 71 71 99 99 99 71 71 21 71 71 99 71 71 99 
99 99 71 71 71 71 71 71 71 71 71 71 71 99 71 71 99 71 71 99 71 99 71 99 71 99 
99 99 71 71 71 71 99 99 99 99 99 71 71 71 71 71 71 71 71 71 71 71 71 71 99 99 
99 99 71 71 99 99 99 71 71 71 99 71 71 71 71 99 71 71 71 71 71 71 71 71 71 99 
99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 

99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 
99 71 99 71 99 71 71 71 71 71 71 71 71 71 99 71 71 71 99 71 71 71 71 71 99 99 
99 71 71 99 71 71 71 71 71 71 71 71 71 71 71 71 71 99 71 71 71 71 71 99 71 99 

99 71 99 99 99 11 99 71 71 71 99 71 71 71 71 71 71 99 99 71 71 71 71 71 71 99 

99 71 71 71 71 15 15 15 71 99 99 71 71 71 71 99 71 71 71 71 71 71 71 71 71 99 

99 71 71 71 71 71 71 15 99 71 71 71 99 71 99 71 99 71 71 71 71 71 71 99 71 99 

99 71 71 71 71 71 71 15 15 15 99 99 71 71 71 71 71 71 71 99 71 71 99 71 71 99 

99 99 71 99 71 71 71 71 71 15 15 15 15 15 15 15 71 99 71 71 71 71 99 71 71 99 

99 71 99 99 99 71 99 71 99 71 71 71 71 71 99 15 71 71 71 71 71 71 71 71 71 99 

99 71 71 71 71 71 71 71 71 71 71 99 71 71 71 15 71 71 71 71 71 71 71 71 71 99 

99 71 71 99 71 71 71 71 71 71 71 71 71 71 71 15 71 71 99 99 71 71 71 71 71 99 

99 71 71 99 71 71 99 99 71 71 71 99 71 71 99 15 99 99 71 71 99 71 71 71 71 99 

99 99 99 71 99 71 99 71 71 71 99 71 71 71 99 15 99 71 99 71 71 71 71 71 71 99 

99 71 71 71 99 99 71 99 71 99 71 71 71 71 71 15 15 15 15 15 71 71 71 71 71 99 

99 71 71 71 71 99 71 71 71 71 71 71 71 71 71 71 71 71 71 15 99 71 71 71 71 99 

99 99 71 71 71 71 71 71 71 99 71 71 71 71 71 71 71 71 71 15 71 71 71 71 71 99 

99 71 71 71 71 71 71 71 71 71 99 99 71 71 99 99 99 71 71 21 71 71 99 71 71 99 

99 99 71 71 71 71 71 71 71 71 71 71 71 99 71 71 99 71 71 99 71 99 71 99 71 99 

99 99 71 71 71 71 99 99 99 99 99 71 71 71 71 71 71 71 71 71 71 71 71 71 99 99 

99 99 71 71 99 99 99 71 71 71 99 71 71 71 71 99 71 71 71 71 71 71 71 71 71 99 

99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 

26