uses
crt;
const
MAXX = 20;
MAXY = 25;
type
TArr = array [0..MAXY, 0..MAXX] of integer;
TCell = record
x: integer;
y: integer;
end;
TListCell = record
x: integer;
y: integer;
G: integer;
parent: TCell;
end;
TListArr = array [1..10000] of TListCell;
TList = record
arr: TListArr;
len: integer;
end;
var
i, j, minind, ind, c: integer;
start, finish: TCell;
current: TListCell;
field: TArr;
opened, closed: TList;
procedure ShowField;
var
i, j: integer;
begin
textcolor(15);
for i := 0 to MAXX do
begin
for j := 0 to MAXY do
begin
case field[j, i] of
99: textcolor(8); // непроходимая
71: textcolor(14); // проходимая
11: textcolor(10); // старт
21: textcolor(12); // финиш
15: textcolor(2); // путь
14: textcolor(5);
16: textcolor(6);
end;
write(field[j, i], ' ');
end;
writeln;
end;
textcolor(15);
end;
procedure AddClosed(a: TListCell);
begin
closed.arr[closed.len + 1] := a;
inc(closed.len);
end;
procedure AddOpened(x, y, G: integer);
begin
opened.arr[opened.len + 1].x := x;
opened.arr[opened.len + 1].y := y;
opened.arr[opened.len + 1].G := G;
inc(opened.len);
end;
procedure DelOpened(n: integer);
var
i: integer;
begin
AddClosed(opened.arr[n]);
for i := n to opened.len - 1 do
opened.arr[i] := opened.arr[i + 1];
dec(opened.len);
end;
procedure SetParent(var a: TListCell; parx, pary: integer);
begin
a.parent.x := parx;
a.parent.y := pary;
end;
function GetMin(var a: TList): integer;
var
i, min, mini: integer;
begin
min := MaxInt;
mini := 0;
for i := 1 to a.len do
if a.arr[i].G < min then
begin
min := a.arr[i].G;
mini := i;
end;
GetMin := mini;
end;
function FindCell(a: TList; x, y: integer): integer;
var
i: integer;
begin
FindCell := 0;
for i := 1 to a.len do
if (a.arr[i].x = x) and (a.arr[i].y = y) then
begin
FindCell := i;
break;
end;
end;
procedure ProcessNeighbourCell(x, y: integer);
begin
if (field[current.x + x, current.y + y] <> 99) then // если проходима
if (FindCell(closed, current.x + x, current.y + y) <= 0) then // и еще не посещена
if (FindCell(opened, current.x + x, current.y + y) <= 0) then // и еще не добавлена в список
begin
AddOpened(current.x + x, current.y + y, current.G + 10);
SetParent(opened.arr[opened.len], current.x, current.y);
end
else
begin
end;
end;
begin
randomize;
for i := 0 to MAXX do
for j := 0 to MAXY do
field[j, i] := 99;
for i := 1 to MAXX - 1 do
for j := 1 to MAXY - 1 do
if random(5) mod 5 = 0 then
field[j, i] := 99
else field[j, i] := 71;
// координаты начальной и конечной позиций
start.x := 5;
start.y := 3;
finish.x := 19;
finish.y := 16;
field[start.x, start.y] := 11;
field[finish.x, finish.y] := 21;
ShowField;
writeln;
opened.len := 0;
closed.len := 0;
AddOpened(start.x, start.y, 0);
SetParent(opened.arr[opened.len], -1, -1);
current.x := start.x;
current.y := start.y;
repeat
minind := GetMin(opened);
current.x := opened.arr[minind].x;
current.y := opened.arr[minind].y;
current.G := opened.arr[minind].G;
DelOpened(minind);
ProcessNeighbourCell(1, 0); // проверить ячейку справа
ProcessNeighbourCell(-1, 0); // проверить ячейку слева
ProcessNeighbourCell(0, 1); // проверить ячейку сверху
ProcessNeighbourCell(0, -1); // проверить ячейку снизу
if (FindCell(opened, finish.x, finish.y) > 0) then
break;
until opened.len = 0;
// считаем и отмечаем обратный путь
c := 0;
while ((current.x <> start.x) or (current.y <> start.y)) do
begin
field[current.x, current.y] := 15;
ind := FindCell(closed, current.x, current.y);
current.x := closed.arr[ind].parent.x;
current.y := closed.arr[ind].parent.y;
inc(c);
end;
ShowField;
writeln(c);
readln;
end.
CnVzZXMKICAgIGNydDsKCmNvbnN0CiAgICBNQVhYID0gMjA7CiAgICBNQVhZID0gMjU7Cgp0eXBlCiAgICBUQXJyID0gYXJyYXkgWzAuLk1BWFksIDAuLk1BWFhdIG9mIGludGVnZXI7CiAgICAKICAgIFRDZWxsID0gcmVjb3JkCiAgICAgICAgeDogaW50ZWdlcjsKICAgICAgICB5OiBpbnRlZ2VyOwogICAgZW5kOwogICAgCiAgICBUTGlzdENlbGwgPSByZWNvcmQKICAgICAgICB4OiBpbnRlZ2VyOwogICAgICAgIHk6IGludGVnZXI7CiAgICAgICAgRzogaW50ZWdlcjsKICAgICAgICBwYXJlbnQ6IFRDZWxsOwogICAgZW5kOwogICAgCiAgICBUTGlzdEFyciA9IGFycmF5IFsxLi4xMDAwMF0gb2YgVExpc3RDZWxsOwogICAgCiAgICBUTGlzdCA9IHJlY29yZAogICAgICAgIGFycjogVExpc3RBcnI7CiAgICAgICAgbGVuOiBpbnRlZ2VyOwogICAgZW5kOwoKdmFyCiAgICBpLCBqLCBtaW5pbmQsIGluZCwgYzogaW50ZWdlcjsKICAgIHN0YXJ0LCBmaW5pc2g6IFRDZWxsOwogICAgY3VycmVudDogVExpc3RDZWxsOwogICAgZmllbGQ6IFRBcnI7CiAgICBvcGVuZWQsIGNsb3NlZDogVExpc3Q7Cgpwcm9jZWR1cmUgU2hvd0ZpZWxkOwp2YXIKICAgIGksIGo6IGludGVnZXI7CmJlZ2luCiAgICB0ZXh0Y29sb3IoMTUpOwogICAgZm9yIGkgOj0gMCB0byBNQVhYIGRvCiAgICBiZWdpbgogICAgICAgIGZvciBqIDo9IDAgdG8gTUFYWSBkbwogICAgICAgIGJlZ2luCiAgICAgICAgICAgIGNhc2UgZmllbGRbaiwgaV0gb2YKICAgICAgICAgICAgICAgIDk5OiB0ZXh0Y29sb3IoOCk7ICAvLyDQvdC10L/RgNC+0YXQvtC00LjQvNCw0Y8KICAgICAgICAgICAgICAgIDcxOiB0ZXh0Y29sb3IoMTQpOyAvLyDQv9GA0L7RhdC+0LTQuNC80LDRjwogICAgICAgICAgICAgICAgMTE6IHRleHRjb2xvcigxMCk7IC8vINGB0YLQsNGA0YIKICAgICAgICAgICAgICAgIDIxOiB0ZXh0Y29sb3IoMTIpOyAvLyDRhNC40L3QuNGICiAgICAgICAgICAgICAgICAxNTogdGV4dGNvbG9yKDIpOyAgLy8g0L/Rg9GC0YwKICAgICAgICAgICAgICAgIDE0OiB0ZXh0Y29sb3IoNSk7CiAgICAgICAgICAgICAgICAxNjogdGV4dGNvbG9yKDYpOwogICAgICAgICAgICBlbmQ7CiAgICAgICAgICAgIHdyaXRlKGZpZWxkW2osIGldLCAnICcpOwogICAgICAgIGVuZDsKICAgICAgICB3cml0ZWxuOwogICAgZW5kOwogICAgdGV4dGNvbG9yKDE1KTsKZW5kOwoKCgpwcm9jZWR1cmUgQWRkQ2xvc2VkKGE6IFRMaXN0Q2VsbCk7CmJlZ2luCiAgICBjbG9zZWQuYXJyW2Nsb3NlZC5sZW4gKyAxXSA6PSBhOwogICAgaW5jKGNsb3NlZC5sZW4pOwplbmQ7CgoKcHJvY2VkdXJlIEFkZE9wZW5lZCh4LCB5LCBHOiBpbnRlZ2VyKTsKYmVnaW4KICAgIG9wZW5lZC5hcnJbb3BlbmVkLmxlbiArIDFdLnggOj0geDsKICAgIG9wZW5lZC5hcnJbb3BlbmVkLmxlbiArIDFdLnkgOj0geTsKICAgIG9wZW5lZC5hcnJbb3BlbmVkLmxlbiArIDFdLkcgOj0gRzsKICAgIGluYyhvcGVuZWQubGVuKTsKZW5kOwoKcHJvY2VkdXJlIERlbE9wZW5lZChuOiBpbnRlZ2VyKTsKdmFyCiAgICBpOiBpbnRlZ2VyOwpiZWdpbgogICAgQWRkQ2xvc2VkKG9wZW5lZC5hcnJbbl0pOwogICAgZm9yIGkgOj0gbiB0byBvcGVuZWQubGVuIC0gMSBkbwogICAgICAgIG9wZW5lZC5hcnJbaV0gOj0gb3BlbmVkLmFycltpICsgMV07CiAgICBkZWMob3BlbmVkLmxlbik7CmVuZDsKCgpwcm9jZWR1cmUgU2V0UGFyZW50KHZhciBhOiBUTGlzdENlbGw7IHBhcngsIHBhcnk6IGludGVnZXIpOwpiZWdpbgogICAgYS5wYXJlbnQueCA6PSBwYXJ4OwogICAgYS5wYXJlbnQueSA6PSBwYXJ5OwplbmQ7CgoKZnVuY3Rpb24gR2V0TWluKHZhciBhOiBUTGlzdCk6IGludGVnZXI7CnZhcgogICAgaSwgbWluLCBtaW5pOiBpbnRlZ2VyOwpiZWdpbgogICAgbWluIDo9IE1heEludDsKICAgIG1pbmkgOj0gMDsKICAgIGZvciBpIDo9IDEgdG8gYS5sZW4gZG8KICAgICAgICBpZiBhLmFycltpXS5HIDwgbWluIHRoZW4KICAgICAgICBiZWdpbgogICAgICAgICAgICBtaW4gOj0gYS5hcnJbaV0uRzsKICAgICAgICAgICAgbWluaSA6PSBpOwogICAgICAgIGVuZDsKICAgIAogICAgR2V0TWluIDo9IG1pbmk7CmVuZDsKCgpmdW5jdGlvbiBGaW5kQ2VsbChhOiBUTGlzdDsgeCwgeTogaW50ZWdlcik6IGludGVnZXI7CnZhcgogICAgaTogaW50ZWdlcjsKYmVnaW4KICAgIEZpbmRDZWxsIDo9IDA7CiAgICBmb3IgaSA6PSAxIHRvIGEubGVuIGRvCiAgICAgICAgaWYgKGEuYXJyW2ldLnggPSB4KSBhbmQgKGEuYXJyW2ldLnkgPSB5KSB0aGVuCiAgICAgICAgYmVnaW4KICAgICAgICAgICAgRmluZENlbGwgOj0gaTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgZW5kOwplbmQ7CgoKcHJvY2VkdXJlIFByb2Nlc3NOZWlnaGJvdXJDZWxsKHgsIHk6IGludGVnZXIpOwpiZWdpbgogICAgaWYgKGZpZWxkW2N1cnJlbnQueCArIHgsIGN1cnJlbnQueSArIHldIDw+IDk5KSB0aGVuICAgIC8vINC10YHQu9C4INC/0YDQvtGF0L7QtNC40LzQsAogICAgICAgIGlmIChGaW5kQ2VsbChjbG9zZWQsIGN1cnJlbnQueCArIHgsIGN1cnJlbnQueSArIHkpIDw9IDApIHRoZW4gLy8g0Lgg0LXRidC1INC90LUg0L/QvtGB0LXRidC10L3QsAogICAgICAgICAgICBpZiAoRmluZENlbGwob3BlbmVkLCBjdXJyZW50LnggKyB4LCBjdXJyZW50LnkgKyB5KSA8PSAwKSB0aGVuIC8vINC4INC10YnQtSDQvdC1INC00L7QsdCw0LLQu9C10L3QsCDQsiDRgdC/0LjRgdC+0LoKICAgICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICAgIEFkZE9wZW5lZChjdXJyZW50LnggKyB4LCBjdXJyZW50LnkgKyB5LCBjdXJyZW50LkcgKyAxMCk7CiAgICAgICAgICAgICAgICBTZXRQYXJlbnQob3BlbmVkLmFycltvcGVuZWQubGVuXSwgY3VycmVudC54LCBjdXJyZW50LnkpOyAKICAgICAgICAgICAgZW5kCiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIGJlZ2luCiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgZW5kOwplbmQ7CgoKYmVnaW4KICAgIHJhbmRvbWl6ZTsKICAgIGZvciBpIDo9IDAgdG8gTUFYWCBkbwogICAgICAgIGZvciBqIDo9IDAgdG8gTUFYWSBkbwogICAgICAgICAgICBmaWVsZFtqLCBpXSA6PSA5OTsKICAgIAogICAgZm9yIGkgOj0gMSB0byBNQVhYIC0gMSBkbwogICAgICAgIGZvciBqIDo9IDEgdG8gTUFYWSAtIDEgZG8KICAgICAgICAgICAgaWYgcmFuZG9tKDUpIG1vZCA1ID0gMCB0aGVuCiAgICAgICAgICAgICAgICBmaWVsZFtqLCBpXSA6PSA5OQogICAgICAgICAgICBlbHNlIGZpZWxkW2osIGldIDo9IDcxOwogICAgCiAgICAvLyDQutC+0L7RgNC00LjQvdCw0YLRiyDQvdCw0YfQsNC70YzQvdC+0Lkg0Lgg0LrQvtC90LXRh9C90L7QuSDQv9C+0LfQuNGG0LjQuQogICAgc3RhcnQueCA6PSA1OwogICAgc3RhcnQueSA6PSAzOwogICAgCiAgICBmaW5pc2gueCA6PSAxOTsKICAgIGZpbmlzaC55IDo9IDE2OwogICAgCiAgICBmaWVsZFtzdGFydC54LCBzdGFydC55XSA6PSAxMTsKICAgIGZpZWxkW2ZpbmlzaC54LCBmaW5pc2gueV0gOj0gMjE7CiAgICAKICAgIFNob3dGaWVsZDsKICAgIAogICAgd3JpdGVsbjsKICAgIAogICAgb3BlbmVkLmxlbiA6PSAwOwogICAgY2xvc2VkLmxlbiA6PSAwOwogICAgQWRkT3BlbmVkKHN0YXJ0LngsIHN0YXJ0LnksIDApOwogICAgU2V0UGFyZW50KG9wZW5lZC5hcnJbb3BlbmVkLmxlbl0sIC0xLCAtMSk7CiAgICBjdXJyZW50LnggOj0gc3RhcnQueDsKICAgIGN1cnJlbnQueSA6PSBzdGFydC55OwogICAgCiAgICByZXBlYXQKICAgICAgICBtaW5pbmQgOj0gR2V0TWluKG9wZW5lZCk7CiAgICAgICAgY3VycmVudC54IDo9IG9wZW5lZC5hcnJbbWluaW5kXS54OwogICAgICAgIGN1cnJlbnQueSA6PSBvcGVuZWQuYXJyW21pbmluZF0ueTsKICAgICAgICBjdXJyZW50LkcgOj0gb3BlbmVkLmFyclttaW5pbmRdLkc7IAogICAgICAgIERlbE9wZW5lZChtaW5pbmQpOyAKICAgICAgICAKICAgICAgICBQcm9jZXNzTmVpZ2hib3VyQ2VsbCgxLCAwKTsgIC8vINC/0YDQvtCy0LXRgNC40YLRjCDRj9GH0LXQudC60YMg0YHQv9GA0LDQstCwCiAgICAgICAgUHJvY2Vzc05laWdoYm91ckNlbGwoLTEsIDApOyAvLyDQv9GA0L7QstC10YDQuNGC0Ywg0Y/Rh9C10LnQutGDINGB0LvQtdCy0LAKICAgICAgICBQcm9jZXNzTmVpZ2hib3VyQ2VsbCgwLCAxKTsgIC8vINC/0YDQvtCy0LXRgNC40YLRjCDRj9GH0LXQudC60YMg0YHQstC10YDRhdGDCiAgICAgICAgUHJvY2Vzc05laWdoYm91ckNlbGwoMCwgLTEpOyAvLyDQv9GA0L7QstC10YDQuNGC0Ywg0Y/Rh9C10LnQutGDINGB0L3QuNC30YMKICAgICAgICAKICAgICAgICBpZiAoRmluZENlbGwob3BlbmVkLCBmaW5pc2gueCwgZmluaXNoLnkpID4gMCkgdGhlbgogICAgICAgICAgICBicmVhazsKICAgIHVudGlsIG9wZW5lZC5sZW4gPSAwOwogICAgCiAgICAvLyDRgdGH0LjRgtCw0LXQvCDQuCDQvtGC0LzQtdGH0LDQtdC8INC+0LHRgNCw0YLQvdGL0Lkg0L/Rg9GC0YwKICAgIGMgOj0gMDsKICAgIHdoaWxlICgoY3VycmVudC54IDw+IHN0YXJ0LngpIG9yIChjdXJyZW50LnkgPD4gc3RhcnQueSkpIGRvCiAgICBiZWdpbgogICAgICAgIGZpZWxkW2N1cnJlbnQueCwgY3VycmVudC55XSA6PSAxNTsKICAgICAgICBpbmQgOj0gRmluZENlbGwoY2xvc2VkLCBjdXJyZW50LngsIGN1cnJlbnQueSk7CiAgICAgICAgY3VycmVudC54IDo9IGNsb3NlZC5hcnJbaW5kXS5wYXJlbnQueDsKICAgICAgICBjdXJyZW50LnkgOj0gY2xvc2VkLmFycltpbmRdLnBhcmVudC55OwogICAgICAgIGluYyhjKTsKICAgIGVuZDsgCiAgICAKICAgIFNob3dGaWVsZDsKICAgIHdyaXRlbG4oYyk7CiAgICByZWFkbG47CmVuZC4=