Advertisement
regergr

Untitled

Nov 25th, 2018
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.47 KB | None | 0 0
  1. program Project1;
  2.  
  3.  
  4. type
  5. point = record
  6. x, y: integer;
  7. end;
  8.  
  9. TData = point;
  10. PListQueue = ^TListQueue;
  11. PListNode = ^TListNode;
  12. TUsed = array of array of boolean;
  13.  
  14. TListQueue = record
  15. head, tail: PListNode;
  16. size: dword;
  17. end;
  18. TListNode = record
  19. next: PListNode;
  20. data: TData;
  21. end;
  22.  
  23. function newListQueue(): PListQueue;
  24. var
  25. p: PListQueue;
  26. begin
  27. new(p);
  28. if (p = nil) then
  29. exit(nil);
  30. p^.head := nil;
  31. p^.tail := nil;
  32. p^.size := 0;
  33. exit(p);
  34.  
  35. end;
  36.  
  37. function pushData(Queue: PListQueue; const Data: TData): boolean;
  38. var
  39. node: plistnode;
  40. begin
  41. new(node);
  42. if (node = nil) then
  43. exit(False);
  44. node^.Data := Data;
  45. node^.Next := nil;
  46. if (Queue^.tail <> nil) then
  47. Queue^.tail^.Next := node;
  48. Queue^.tail := node;
  49. Queue^.size += 1;
  50.  
  51. if (Queue^.head = nil) then
  52. Queue^.head := Queue^.tail;
  53. exit(True);
  54.  
  55. end;
  56.  
  57. function popData(Queue: PListQueue): boolean;
  58. var
  59. node: plistnode;
  60. begin
  61. if (Queue^.head = nil) then
  62. exit(False);
  63. node := queue^.head;
  64. Queue^.head := node^.Next;
  65. dispose(node);
  66. queue^.size -= 1;
  67. exit(True);
  68.  
  69. end;
  70.  
  71. function getData(Queue: PListQueue): TData;
  72. begin
  73. exit(Queue^.head^.Data);
  74. end;
  75.  
  76. function getSize(const Queue: PListQueue): dword;
  77. begin
  78. exit(Queue^.size);
  79. end;
  80. /////////////////
  81. procedure Make_path(q: PListQueue; p: point; n, m: integer; used: TUsed);
  82. var
  83. buf: point;
  84. begin
  85. if (p.x > 0) then
  86. begin
  87. if (used[p.x, p.y]) then
  88. begin
  89. buf.x := p.x + 1;
  90. buf.y := p.y;
  91. writeln('(', buf.x, ',', buf.y, ')');
  92. end;
  93. end
  94. else if (p.x < n) then
  95. begin
  96. if (used[p.x, p.y]) then
  97. begin
  98. buf.x := p.x - 1;
  99. buf.y := p.y;
  100. writeln('(', buf.x, ',', buf.y, ')');
  101. end;
  102. end
  103. else if (p.y < n) then
  104. begin
  105. if (used[p.x, p.y]) then
  106. begin
  107. buf.x := p.x;
  108. buf.y := p.y + 1;
  109. writeln('(', buf.x, ',', buf.y, ')');
  110. end;
  111. end
  112. else if (p.y > 0) then
  113. begin
  114. if (used[p.x, p.y]) then
  115. begin
  116. buf.x := p.x;
  117. buf.y := p.y - 1;
  118. writeln('(', buf.x, ',', buf.y, ')');
  119. end;
  120. end;
  121. end;
  122.  
  123. var
  124. n, m, len, lengthQ: integer;
  125. x, y, i, j: integer;
  126. A: array of array of char;
  127. q: PListQueue;
  128. p, buf: point;
  129. used: array of array of boolean;
  130. begin
  131. Assign(input, 'test4.txt');
  132. Assign(output, 'output.txt');
  133. reset(input);
  134. rewrite(output);
  135. len := 0;
  136. lengthQ := 0;
  137. readln(n, m);
  138. readln(i, j);
  139. SetLength(used, n, m);
  140. for y := 0 to n do
  141. begin
  142. for x := 1 to m + 1 do
  143. begin
  144. used[x, y] := False;
  145. end;
  146. end;
  147. SetLength(A, n, m);
  148. q := NewListQueue();
  149. for y := 0 to n do
  150. begin
  151. for x := 1 to m + 1 do
  152. begin
  153. Read(A[x, y]);
  154. end;
  155. readln();
  156. end;
  157. p.x := i;
  158. p.y := j;
  159. PushData(q, p);
  160. used[p.x, p.y] := True;
  161. while (getSize(q) > 0) do
  162. begin
  163. if (p.x + 1 > x) or (p.x - 1 < 0) or (p.y + 1 > y) or (p.y - 1 < 0) then
  164. begin
  165. Make_path(q, p, n, m, used);
  166. Exit;
  167. end
  168. else
  169. begin
  170. p := GetData(q);
  171. PopData(q);
  172. if (A[p.x + 1, p.y] = ' ') then
  173. begin
  174. buf.x := p.x + 1;
  175. buf.y := p.y;
  176. if not (used[buf.x, buf.y]) then
  177. PushData(q, buf);
  178. end;
  179. if (A[p.x - 1, p.y] = ' ') then
  180. begin
  181. buf.x := p.x - 1;
  182. buf.y := p.y;
  183. if not (used[buf.x, buf.y]) then
  184. PushData(q, buf);
  185. end;
  186. if (A[p.x, p.y + 1] = ' ') then
  187. begin
  188. buf.x := p.x;
  189. buf.y := p.y + 1;
  190. if not (used[buf.x, buf.y]) then
  191. PushData(q, buf);
  192. end;
  193. if (A[p.x + 1, p.y - 1] = ' ') then
  194. begin
  195. buf.x := p.x;
  196. buf.y := p.y - 1;
  197. if not (used[buf.x, buf.y]) then
  198. PushData(q, buf);
  199. end;
  200.  
  201. end;
  202.  
  203. end;
  204. write('no exit');
  205. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement