Может кто подскажет...

← →
Oleg © (2010-01-27 13:26) [0]

Здравствуйте.
Может кто подскажет, или натолкнет на правильную мысль. :-)

Есть такая игра Clix, или Kubes и т.д. (названий у нее много). Смысл в том: есть некоторое поле размерами m X n (максимум 25 X 15), заполненное кубиками разных цветов (количество цветов максимум 8). При клике на одноцветную область ( от 2 и более стоящих рядом одноцветных элементов), эта область пропадает, а все остальные "кубики" смещаются сначала вниз насколько возможно, потом влево. Игра ведется либо на очки (чем большую область убирать за один раз, тем больше очков), либо, чтобы очистить все поле. Надо:
1. Найти последовательность наименьшей длины, которая приводит к полной очистке поля, или доказать, что такой последовательности нет.
2. Найти последовательность, при которой будет набрано наибольшее количество очков, очки считаются как a*x^b, где x - количество кубиков в убираемой цветовой области, a и b - некоторые константы.

Нужна идея, как это реализовать. Полный перебор решает задачу, но возможных вариантов здесь оченьо много. :-( А как ограничить количество вариантов пока не придумать.

← →
Ega23 © (2010-01-27 13:52) [1]

Что-то мне подсказывает, что решение как-то с нахождением "путей Гамильтона" в графе связано.

← →
Oleg © (2010-01-27 14:38) [2]

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

Перебор у тебя будет полюбому. Т.е. кол-во узлов у графа равно кол-ву кубиков. А вот дальше - интереснее.

Может кто подскажет... Найти похожие ветки