IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Ученая блоха, Волновой алгоритм
сообщение
Сообщение #1


Гость






Помогите пожалуйста. wub.gif Нужно решить следующую задачу:
Ученая блоха. Дан квадрат размером n x n, в клетки которого вписаны числа от 1 до 9. По клеткам прыгает ученая блоха, причем, прыжки она делает, строго подчиняясь следующим правилам:
- блоха никогда не прыгает за пределы квадрата;
- с клетки, в которую вписано число k блоха прыгает ровно на k клеток по вертикали или горизонтали.
Например, в приведенном ниже квадрате, блоха может с центральной клетки прыгнуть на любую из выделенных клеток. попав на клетку с цифрой 7, блоха будет оставаться на ней вечно, так как при любом прыжке она выйдет за границы квадрата, что недопустимо.
4 2 1 4 1
1 2 3 5 2
7 1 2 1 2
4 3 4 7 3
4 5 3 2 5
Напишите алгоритм, который по заданному квадрату, координатам блохи и клетки с блошиным завтраком определяет:
1. возможно ли блохе позавтракать;
2. если позавтракать возможно, то определить один из кратчайших путей блохи в виде последовательности координат клеток, которые блоха посетит на пути к завтраку.

у меня почему-то при тестировании матрицы, заполненной единицами выдает неверную матрицу,заполненную волновым алгоритмом на последних шагах.


program bloha;
uses crt;
type mas=array[1..10,1..10] of integer;
mass=array[1..20] of string;
var a,p,p1:mas; n,m1,m2,m3,m4,t:integer; q,q1,min1,min2:mass;

procedure vvod(n:integer; var a:mas);
var i,j:integer;
begin
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
end;

procedure vyvod(n:integer; a:mas);
var i,j:integer;
begin
for i:=1 to n do
begin
for j:=1 to n do
write(a[i,j],' ');
writeln;
end;
end;

procedure prisv(n:integer;p:mas;var p1:mas);
var i,j:integer;
begin
for i:=1 to n do
for j:=1 to n do
p1[i,j]:=p[i,j];
end;

procedure pryg(h,k,i,j,n:integer;a,p:mas; var p1:mas);
var h1,h2,h3,h4,k1,k2,k3,k4:integer;
begin
k1:=k+1;
k2:=k+1;
k3:=k+1;
k4:=k+1;
if h<>0 then
begin
if (i-h)>0 then
begin
if p[i-h,j]=0 then
begin
p[i-h,j]:=k1; h1:=a[i-h,j];
end
else begin k1:=k; h1:=0; end;
end;
if (i+h)<=n then
begin
if p[i+h,j]=0 then
begin
p[i+h,j]:=k2; h2:=a[i+h,j];
end
else begin k2:=k; h2:=0; end;
end;
if (j-h)>0 then
begin
if p[i,j-h]=0 then
begin
p[i,j-h]:=k3; h3:=a[i,j-h];
end
else begin k3:=k; h3:=0; end;
end;
if (j+h)<=n then
begin
if p[i,j+h]=0 then begin
p[i,j+h]:=k4; h4:=a[i,j+h];
end
else begin k4:=k; h4:=0; end;
end;
end;
if h<>0 THEN begin
if (i-h)>0 then pryg(h1,k1,(i-h),j,n,a,p,p);

if (j-h)>0 then pryg(h3,k3,i,(j-h),n,a,p,p);
if (i+h)<=n then pryg(h2,k2,(i+h),j,n,a,p,p);
if (j+h)<=n then pryg(h4,k4,i,(j+h),n,a,p,p);end;

prisv(n,p,p1);
end;


procedure put(c1,c2,c3,c4,n,t:integer;a,p:mas);
var i,j,k,l:integer;
begin
if t>0 then
begin
if a[c3,c4]>0 then writeln(t,' ',c3,' ',c4);
if (c1<>c3) and (c2<>c4) then
begin
k:=p[c3,c4];
for i:=1 to n do
for j:=1 to n do
if p[i,j]=k-1 then
begin
l:=a[i,j]; if (c3-l=i) or (c4-l=j) or (c3+l=i) or (c4+l=j)
then begin put(c1,c2,i,j,n,(t-1),a,p); end else
end;
end;
end;
end;

procedure bloh(c,c1,b1,b2,n:integer; var p1:mas);{koordinaty na4ala i konca}
var k,i,j:integer;
begin
for i:=1 to n do
for j:=1 to n do
p[i,j]:=0; p[c,c1]:=1;
k:=a[c,c1];
pryg(k,1,c,c1,n,a,p,p1);
if p[b1,b2]<>0 then
begin
writeln('da');
writeln(p[b1,b2],' kol-vo shagov');
end
else writeln('net');
end;

begin
clrscr; {n:=3;}write('vvedite n=');read(n);
vvod(n,a);
clrscr;
vyvod(n,a);
writeln('gde nahoditsya bloha?'); readln(m1,m2);
writeln('a gde zavtrak?'); readln(m3,m4);
bloh(m1,m2,m3,m4,n,p); t:=p[m3,m4]; put(m1,m2,m3,m4,n,t,a,p);
writeln; vyvod(n,p);
end.
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 3:00
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name