Мины, Динамическое программирование Опции

[setare]

Здравствуйте! Нам дали задачу на динамическое программирование толком не обьяснив как можно эту тему использовать в решении задач. Мне дали следующую задачу:
Есть строка, которую вводит пользователь, например: 1 2***3*1 После этого надо написать программу, которая бы сосчитала сколькими способами можно поставить мины, как в игре сапере под каждой цифрой. Как можно подойти к этой задаче? И как рассчитать эти способы? А также массив будет двумерный или одномерный только для самых мин? Спасибо за ответ! И я пользовалась поиском, но по-моему такой темы у вас не была. По крайней мере я ничего не нашла.

Сообщение отредактировано: setare - 12.12.2005 23:52

[Lapp]

Сапёр, или WinMine - игрушка, входящая в стандартный набор игр Windows любой версии. lapp, неужели ни разу не играл?! Какая у тебя ОС?

Играл! давно было, но - было.. Более того, я ее как-то раз сделал в полном варианте и в графике за пару-тройку часов, пока объяснял одному человеку программирование. Ее название вообще-то minesweeper, и у меня никогда не было русской винды - может, поэтому не проассоциировало.. А может потому, что она мне казалась существенно двумерной (но я был не прав). Еще в заблуждение вводила 4-ка, мозолившая глаза с самого начала - в двумерной версии четверки никак не может быть. Ок, спасибо всем, растолковали.
Malice, твоя прога тоже помогла пониманию (собственно, главным образом именно она), я ее полностью разобрал. Она прекрасно работает, но весьма неоптимальна, а динамическое программирование - это как раз определенный метод оптимизации. Похоже, тут его можно применить, но надо чуть-чуть покумекать.. Беру небольшой тайм-аут

[Malice]

Она прекрасно работает, но весьма неоптимальна, а динамическое программирование - это как раз определенный метод оптимизации.

Не знаю, над оптимизацией я обычно не заморачиваюсь. Это нужно написать, а потом вторым проходом оптимизировать, а на это времени нет обычно, да и интерес пропадает. Хотя что-то мне подсказывает, что после оптимизации эта программа станет больше