Задача, не очень сложная. Игра Змея.

← →
Vlad Oshin © (2005-01-17 12:09) [0]

Вчера от нечего делать играл с мобильником

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

Понятное дело, надо ходить, экономя место. Очевидно, что игра будет выиграна, если найдется траектория, обходящая всю матрицу, непересекающаяся сама с собой, и заканчивающаяся в исходной точке.
Возможны 2 случая.
1. Одна из размерности матрицы четная. Тогда траектория легко может быть установлена.
2. Обе размерности нечетные.
Вопрос:
1.Найдется ли для этого случая требуемая траектория?
2.Можно ли выиграть, если таковой не существует? (весь экран занят змеей и компьютеру некуда поставить кролика)

← →
Думкин © (2005-01-17 12:14) [1]

Зачем в исходной заканчивающаяся? Что-то спиральное подойдет?

← →
Думкин © (2005-01-17 12:16) [2]

Хотя да. Хвост-то тоже движется. :(

← →
Vlad Oshin © (2005-01-17 12:18) [3]

Подойдет
Просто предложенная мной траектория очевидно выигрывает.

ЗЫ
алгоритм движения змеи есть

← →
Vlad Oshin © (2005-01-17 12:23) [4]

т.е. выигрышный :)
т.е. мне так показалось вчера :)

← →
KSergey © (2005-01-17 12:24) [5]

Спираль не подойдет явно. Особенно, если закрутиться - внутрь, от края ;)
В правилах (или реализации) есть еще такой нюанс: выход за границу экрана приводит

а) к проигрышу
б) к продолжению движения в том же направлении. но с противиположной стороны экрана.

Видимо это тоже надо учитывать (или хотя бы озвучить этот нюанс).

PS
Мне больше нравится второй ;) Ну в смысле - поиграть

← →
uw © (2005-01-17 12:27) [6]

>Vlad Oshin © (17.01.05 12:09)

А сканировать, как в телевизоре, не пробовал?

← →
KSergey © (2005-01-17 12:29) [7]

> [6] uw © (17.01.05 12:27)
> А сканировать, как в телевизоре, не пробовал?

Не выйдет

← →
uw © (2005-01-17 12:30) [8]

Почему?

← →
KSergey © (2005-01-17 12:31) [9]

> [8] uw © (17.01.05 12:30)
> Почему?

Дошли до нижнего правого угла, дальше что?

← →
uw © (2005-01-17 12:32) [10]

То же, что и раньше. Там же стенки прозрачные.

← →
Думкин © (2005-01-17 12:34) [11]

> [5] KSergey © (17.01.05 12:24)

Да, со спиралью - поспешил. Я думал - типа трепаться надо, а оказывается Влад уже решил и просит последовать за ним.
Про ньюансы - верно.
Ну если одна четная - он написал.
А если нечетные обе и надо чтобы весь экран был занят змеей. Если есть траектория - то ясно. Если нет. То как можно занять весь экран змеей? Ведь если двинулись - заяц - удлинились - весь экран, - что заполнило клетку с которой ушел хвост? Если новое - то траектория требуема. Если голова - то значит там был жо этого заяц. Или что-то я не так понял?

> [11] Думкин © (17.01.05 12:34)

Чего-то я ничего не понял ;)
Ладно, если полегчает: обычно реализация такова, что при входе головы на клетку с кроликом ничего не удлинняется, а просто голова далее движется, а последний элемент хвоста тут (на этой итерации) как-бы не стирается...

Траектория, очевидно, должна быть замкнутой. Возможно - с учетом прозрачности стенок, если они таковы. Если я все правильно понимаю.

нет, стенки не прозрачны и выход с экрана - проигрыш.
как возможно с незамкнутостью траектории:

пример

н т5 т6
т1 т4 т7
т2 т3 к

н - начало
тК - тело
к - конец
итого: 3х3, весь экран занят, незамкнута, кролика некуда поставить.
Как такое или подобное получить?

Необязательно делать траекторию постоянную. Мое решение - в одном случаие, при отпределенном условии, траектория меняется на одну клетку.

> [13] Vlad Oshin © (17.01.05 12:59)
> Как такое или подобное получить?

Дык потому я говорю о необходимости замкнутости (но не постоянстве!) траектории, что к такой ситуации надо еще прийти.
По-моему, к такой прийти просто невозможно.

> Дык потому я говорю о необходимости замкнутости

Да, замкнута.

далее можно не читать! подсказка

дувям сопсбоаим.
Как повяляестя псолендий корлки - она рамзыкатеся, корлки сеъдеастя, земя улдинеятяс полесдинй раз, экарн азоплнен.

http://www.oshin.nightmail.ru/Zmeja.JPG

Задача, не очень сложная. Игра Змея. Найти похожие ветки