Сломалась программа

@Prospek · Регистрация: 21.04.2019

Author24 — интернет-сервис помощи студентам

Рассмотрим следующую игру:

Имеется доска, разделенная на клетки. В каждой клетке стоит некоторое число. Из одной клетки можно перейти в другую, если расстояние между этими клетками равно числу в той клетке, куда делается ход. Игрок начинает ходить из клетки (X1,Y1).

Определить за какое минимальное количество ходов игрок может переместиться в клетку (X2,Y2). Расстояние между клетками (A,B) и (C,D) вычисляется по формуле: abs(C-A)+abs(D-B) (здесь abs - это модуль числа, т.е. abs(-5)=5, abs(7)=7, abs(0)=0).

Ограничения:
1 <= N,M <= 30
1 <= X1,X2 <= N
1 <= Y1,Y2 <= M
Формат ввода:
N M - размер доски по вертикали и горизонтали.
A11 A12 ... A1m
A21 A22 ... A2m - числа в соответствующих клетках доски.
...
An1 An2 ... Anm
X1 Y1 X2 Y2
Формат вывода:
L - минимальное количество ходов.

Pascal

program c;
var
Que:array[1..900,1..3] of longint;
Marked:array [1..30,1..30] of boolean;
Know:array [1..30,1..30,1..30,1..30] of boolean;
Sx,Sy,Ex,Ey,x,y,StepNumber,n,m,QueBegin,QueEnd:longint;
Found:boolean;
procedure Put(x,y,StepNumber : longint);
begin
Inc(QueEnd);
Que[QueEnd,1]:=x;
Que[QueEnd,2]:=y;
Que[QueEnd,3]:=StepNumber;
Marked[x,y]:=true;
end;
procedure Get(var x,y,StepNumber:longint);
begin
x:=Que[QueBegin,1];
y:=Que[QueBegin,2];
StepNumber:=Que[QueBegin,3];
Inc(QueBegin);
end;
Procedure PutALL(x,y,StepNumber:longint;var Found:boolean);
var i,j:longint;
begin
Found:=false;
for i:=1 to n do
     for j:=1 to m do
       begin
         Found := (i = Ex) and (j = Ey) and (Know[x,y,i,j]);
         if Found then exit;
         if (not Found) and (Know[x,y,i,j]) and
            (not Marked[i,j])
           then  Put(i,j,StepNumber);
       end;
end;
Procedure StartProcess;
var
Temp:array[1..30,1..30] of longint;
i,j,x,y:longint;
begin
readln (n,m);
for i:=1 to n do
for j:=1 to m do
for x:=1 to n do
for y:=1 to m do
if abs(i-x)+ abs(j-y)=Temp[x,y]
then Know[i,j,x,y]:=true
else Know[i,j,x,y]:=false;
for i:=1 to n do
for j:=1 to m do
Marked[i,j]:= false;
QueBegin:=1;
QueEnd:=0;
end;
Begin
StartProcess;
StepNumber:=0;
Found:=(Sx=Ex) and (Sy=Ey) and (Know[Sx,Sy,Ex,Ey]);
Put(Sx,Sy,StepNumber);
while (not Found) and (QueBegin(QueEnd)) do            //<------------------------------------------------------------------------
begin
Get(x,y,StepNumber);
Inc(StepNumber);
PutAll(x,y,StepNumber,Found);
end;
Writeln(StepNumber);
end.

Ошибка:Ожидалось имя процедуры или функции

@Пс · 22.04.2019, 20:04

Prospek, на какой строке вылазит ошибка?

Добавлено через 2 минуты
понял.

Добавлено через 2 минуты

Сообщение от Prospek

Pascal

1	(QueBegin(QueEnd))

что за не понятные действия с переменными?!

@Prospek · 22.04.2019, 20:21 **[ТС]**

Там опечатка
(QueBegin<=QueEnd)

@Пс · 22.04.2019, 20:55

Prospek, проблема решена?

@Prospek · 22.04.2019, 22:50 **[ТС]**

Пс,
Пример ввода:
2 2
1 2
2 2
1 1 2 2
Пример вывода:
1

Pascal

program c;
var
Que:array[1..900,1..3] of longint;
Marked:array [1..30,1..30] of boolean;
Know:array [1..30,1..30,1..30,1..30] of boolean;
Sx,Sy,Ex,Ey,x,y,StepNumber,n,m,QueBegin,QueEnd:longint;
Found:boolean;
procedure Put(x,y,StepNumber : longint);
begin
Inc(QueEnd);
Que[QueEnd,1]:=x;
Que[QueEnd,2]:=y;
Que[QueEnd,3]:=StepNumber;
Marked[x,y]:=true;
end;
procedure Get(var x,y,StepNumber:longint);
begin
x:=Que[QueBegin,1];
y:=Que[QueBegin,2];
StepNumber:=Que[QueBegin,3];
Inc(QueBegin);
end;
Procedure PutALL(x,y,StepNumber:longint;var Found:boolean);
var i,j:longint;
begin
Found:=false;
for i:=1 to n do
     for j:=1 to m do
       begin
         Found := (i = Ex) and (j = Ey) and (Know[x,y,i,j]);
         if Found then exit;
         if (not Found) and (Know[x,y,i,j]) and
            (not Marked[i,j])
           then  Put(i,j,StepNumber);
       end;
end;
Procedure StartProcess;
var
Temp:array[1..30,1..30] of longint;
i,j,x,y:longint;
begin
readln (n,m);
for i:=1 to n do
for j:=1 to m do
for x:=1 to n do
for y:=1 to m do
if abs(i-x)+ abs(j-y)=Temp[x,y]
then Know[i,j,x,y]:=true
else Know[i,j,x,y]:=false;
for i:=1 to n do
for j:=1 to m do
Marked[i,j]:= false;
QueBegin:=1;
QueEnd:=0;
end;
Begin
StartProcess;
StepNumber:=0;
Found:=(Sx=Ex) and (Sy=Ey) and (Know[Sx,Sy,Ex,Ey]);
Put(Sx,Sy,StepNumber);
while (not Found) and (QueBegin<=QueEnd) do           
begin
Get(x,y,StepNumber);
Inc(StepNumber);
PutAll(x,y,StepNumber,Found);
end;
Writeln(StepNumber);
end.

Но при заполнении данных вылезает ошибка
Ошибка времени выполнения: Индекс находился вне границ массива.

@Пс · 23.04.2019, 15:13

Prospek, в какой строке ошибка?

Добавлено через 5 часов 26 минут

Сообщение от Prospek

Pascal

1	Found:=(Sx=Ex) and (Sy=Ey) and (Know[Sx,Sy,Ex,Ey]);

а что эта строка делает?

ФедосеевПавел · 23.04.2019, 16:22

Prospek, мне кажется, что решение задания в реализации так называемом поиске в ширину (волновом методе).
Если "перевернуть" условие задачи, то получится поиск решения от точки (X2,Y2) в точку (X1,Y1).

Ощущение, что именно его вы и пытаетесь реализовать.

Что-то похожее по смыслу - Найти наиболее короткий из путей от первой до второй клетки, двигаясь ходом коня - "Найти наиболее короткий из путей от первой до второй клетки, двигаясь ходом коня"
Там волновой алгоритм - каждая новая клеточка, на которую возможен переход помещается в очередь (волну). Саму очередь можно реализовать и на массиве.

Только вам следовало бы проще определять клеточки, на которые возможен переход.
Вот предположим, что в клеточке (X, Y) число N.
Крайняя левая клеточка, в которую возможен переход - (X-N, Y).
Делаем "шаг вправо" - таких клеточек уже две (X-N+1, Y-1) и (X-N+1, Y+1).
Таким образом, обозначив dX перемещение от крайней левой клеточки в цикле получим все доступные для перехода

Pascal

for dX:=-N to N do
begin
  обработка клеточки (X-dX, Y+N-dX)
  обработка клеточки (X-dX, Y+N+dX)
end;

Добавлено через 7 минут
По сути, ход конём является ходом из клетки с числом 3, только отсутствуют ещё 4 случая для ровных ходов ("ладьёй").

@Prospek 0 / 0 / 0 Регистрация: 21.04.2019 Сообщений: 35
	22.04.2019, 20:21 [ТС]	3
	Там опечатка (QueBegin<=QueEnd) 0

@Пс 257 / 149 / 70 Регистрация: 29.07.2018 Сообщений: 1,246
	22.04.2019, 20:55	4
	Prospek, проблема решена? 0

	23.04.2019, 16:22