Интересная задачка

~AquaZ~ · 01-12-2010 23:19

Есть объект, например, жук. Лабиринт - матрица XxY ячеек. Жук стартует в точке (0;0), заканчивает движение в правой нижней точке. Алгоритм движения:

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

Каким должен быть лабиринт (за исключением закрытого), в котором жук проведёт больше всего времени?

3Doomer · 02-12-2010 11:25

не вижу простора для мысли...лабиринт всегда прямоугольный, и выход со входом всегда по углам. что менять-то можно? размер?
тогда проведённое время будет прямо пропорционально размеру лабиринта

~AquaZ~ · 02-12-2010 13:59

Забыл сказать, каждая ячейка матрицы может быть занятой (стенка, туда нельзя идти) или свободной.

3Doomer · 02-12-2010 16:25

хм...судя по алгоритму движения, он пройдёт от старта до упора вниз, потом направо - прямо к финишу

надо перегораживать дорогу...первым делом - на одну ниже старта, а потом - хз...

Den_spb · 02-12-2010 19:20

Ответа к задаче не знаю, но могу дать свою загадку:

Что за предмет изображён на рисунке? Форма предмета доведена достаточно достоверно.

~AquaZ~ · 02-12-2010 20:40

Круг и квадрат smile
...или...
круг, в котором высверлен квадрат smile )

Den_spb · 02-12-2010 22:42

Круг и квадрат - геометрические фигуры, а тут изображён материальный предмет (кстати, знакомый всем).

~AquaZ~ · 02-12-2010 23:33

Не знаю. Закончили оффтоп.
Как проверить, не отделён ли жук от выхода?

~AquaZ~ · 08-12-2010 21:05

Есть тут кто?

SannyBuilder.com Forums

#1 01-12-2010 23:19

Интересная задачка

#2 02-12-2010 11:25

Re: Интересная задачка

#3 02-12-2010 13:59

Re: Интересная задачка

#4 02-12-2010 16:25

Re: Интересная задачка

#5 02-12-2010 19:20

Re: Интересная задачка

#6 02-12-2010 20:40

Re: Интересная задачка

#7 02-12-2010 22:42

Re: Интересная задачка

#8 02-12-2010 23:33

Re: Интересная задачка

#9 08-12-2010 21:05

Re: Интересная задачка

Board footer