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

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

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

 
 Ответить  Открыть новую тему 
> Лабиринт, интеллектуальная Задача
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


ЛЮДИ ОТКЛИКНИТЕСЬ!!! Помогите пожалуйста с задачей. Не могу написать его на паскале. Имеется алгоритм
Матрица размера N*M определяет некоторый лабиринт. B матице элемент 1 обозначает стену, а 0 определяет свободное место. В первой строке матрицы определяются входы x(i), а в последней выходы y(i), i=1,..,k, которые должны быть нулевыми элементами.

Необходимо определить, можно ли

а) провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза.

б) то же, но человека можно выводить чеpез любой из выходов. Примечание: Движение в лабиринте осуществляется только по вертикали или горизонтали.

Алгоритм:
Основная стратегия человека, вошедшего в самый левый вход, состоит в прохождении лабиринта, используя наиболее левые свободные места лабиринта, т.е. он должен двигаться, держась правой рукой за "стенку" лабиринта. Этот процесс можно формализовать следующим образом. Находясь в очередной позиции лабиринта, он должен помнить, с какой стороны он пришел сюда (слева, справа, сверху, снизу), и, руководствуясь этой информацией, вобрать следующее наиболее предпочтительное направление в новую позицию (куда он может пойти и где еще не был). При этом удобно использовать стек, в верхушке которого находятся координаты текущей позиции и направление, по которому в нее пришли. При этом все посещенные клетки метятся. Легко заметить, что если в позицию попали сверху, то наилучшим направлением будет налево, затем вниз, направо, и наконец назад (вверх). Аналогично можно определить наилучшие направления для других случаев.
Эта стратегия повторяется каждым из людей, при этом позиции, помеченные предыдущими людьми, считаются запрещенными для следующих.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской

Репутация: -  0  +


Возможно, это тебе поможет:

http://tpxexe.narod.ru/020.html

Сообщение отредактировано: Connected -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


Спасибо!! Это хоть что-то! Но мне по заданию нужно провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской

Репутация: -  0  +


К сожалению, я больше ничего подсказать не в силах..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Задачка меня заинтересовала - я вообще питаю слабость к лабиринтам.. smile.gif
Сначала - видимо, у тебя опечатка:
Цитата(Andrej_87 @ 19.03.2007 21:07) *

.. он должен двигаться, держась правой рукой за "стенку" лабиринта.
- наверное, ты имел в виду левую руку. В остальном агоритм в целом правильный. Добавлю только, что рассмотрение "откуда пришел" гораздо легче формализовать, если рассматривать векторное представление. Вектор "скорости" представляет собой пару (dx,dy). Если этот вектор не меняется - то он прибавляется на следующем ходу, представляя движение в прежнем направлении. Но нам нужно:

1. Повернуться налево и попробовать идти.
2. Если не получается, то повернуться направо.
3. Если снова не получается - перейти к п.2

Вот и весь алгоритм. Повороты векторов тривиально делаются обычной матрицей поворота с синусами/косинусами, только тут она состоит из единиц, нулей и минус единиц..

Выкладываю программу прохождения, которую я сваял на скорую руку. Повороты реализованы процедурой. Шаг - тоже (только для ясности). Данные берутся из файла и выглядят примерно так (мой тестовый файл):
1101111110111111111011111111101111111111
1101111110111111111011111111100011111111
1101111100111000100011111110111011111111
1101110001111010101111111110000011111111
1101110011111010100000011111101111111111
1101111001111010111111011111101110000011
1101111101111010111111011100000000111011
1101111101111010000000011101111101111011
1101111100000011111111111101111100000011
1101111100011000000011111101111111111111
1101111111111000000000111100000111111111
1100011111000000000011111111110111111111
1111000000011100000111110000000000000111
1111011111000000111111110111111101110111
1111011111011110111000000000000001110111
1111000000011110000011101101111100000111
1111111111011111111110001101111111111111
1111111111011111111110111100000111111111
1111111111011111100000111111110111111111
1111111111011111101111111111110111111111

Размеры определяются автоматически из файла.
Заметьте, что собственно лабиринт тут окружен бордюром шириной 1 символ. Это значит, что на вертикальных краях нулей встречаться не должно, нули на верхней кромке представляют входы (вместо массива X(i) ), а нули на нижней кромке - выходы (вместо массива y(i) ).
Это все надо записать в файл с названием Labyrinth_0_0.dat

При выводе я уделил достаточное внимание наглядности smile.gif.
Далее сама прога..
uses
CRT;

const
mx=100; nx=100;
Left=1; Right=-1;
Trace=-1;

type
tLabyrinth=array[0..mx,0..nx]of integer;

var
m,n,m1,n1,x,y,dx,dy,k,l,x0,i,j:integer;
Lab:tLabyrinth;
f:text;
c:char;

procedure Show;
var
i,j:integer;
begin
for j:=0 to n1 do begin
for i:=0 to m1 do begin
l:=Lab[i,j];
if l>0 then begin
TextColor(l+7);
Write('*');
TextColor(7)
end
else if l=0 then Write(' ')
else Write('#');
end;
WriteLn
end
end;


procedure Turn(dir:integer; var x,y:integer);
var
z:integer;
begin
z:=x;
x:=dir*y;
y:=-dir*z
end;


procedure Step(var x,y,dx,dy:integer);
begin
Turn(Left,dx,dy);
while Lab[x+dx,y+dy]>0 do Turn(Right,dx,dy);
x:=x+dx;
y:=y+dy
end;


begin
{Read the data file}
Assign(f,'labyrinth_0_0.dat');
ReSet(f);
m1:=-1;
while not EoLn(f) do begin
Read(f,c);
Inc(m1);
case c of
'1',' ': Lab[m1,0]:=1;
'0': Lab[m1,0]:=0
end
end;
ReadLn(f);
n1:=0;
while not EoF(f) do begin
Inc(n1);
for i:=0 to m1 do begin
Read(f,c);
case c of
'1',' ': Lab[i,n1]:=1;
'0': Lab[i,n1]:=0
end
end;
ReadLn(f)
end;
m:=m1-1; n:=n1-1;
Close(f);

{Passing}
k:=0;
WriteLn('Labyrinth ',m,'x',n);
{Probing all the entries}
for x0:=m downto 1 do if Lab[x0,0]=0 then begin
Inc(k);
x:=x0;
y:=1;
dx:=0;
dy:=1;
while (y>0)and(y<n1) do begin
Inc(Lab[x,y],Trace);
Step (x,y,dx,dy);
end;
Write('Entry ',k,': ');
if y=0 then WriteLn('No way!') else WriteLn('Passed.');
for j:=1 to n do for i:=1 to m do if Lab[i,j]<0 then Lab[i,j]:=k+1;
Show;
Write('Press Enter..');
ReadLn;
WriteLn
end;
WriteLn('Done.')
end.



--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Большое спасибо!!!
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Фанат Delphi
**

Группа: Пользователи
Сообщений: 72
Пол: Мужской
Реальное имя: Сергей

Репутация: -  0  +


Lapp, гениально good.gif


--------------------
ICQ (384-043-857)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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