Аля Сапёр, олимпиадная задача Опции

[hardcase]

Вот задача про "Минное поле чудес" (постил Я) брутальная задачка
Меня интересует просто алгоритм. Честно говоря я не представляю, как её можно сделать.

Конечно, сперва надо действовать как в игре Сапёр - с этим проблем нету.
Проблема - как потом считать вероятности?

Сообщение отредактировано: hardcase - 25.01.2006 14:20

[Lapp]

Ага, я подозревал, что задача про расстановки мин появилась неспроста! Вот и продолжение..
Вот тут я решал задачу про расстановку мин, но правда не в прямоугольнике, а линейную (причем, по требованию клиента, решил двумя способами..). Думаю, переделать в двумерный вариант не очень сложно.

Далее, по мере просмотра вариантов нужно просто считать количество мин для каждой клетке. Поясняю. Сначала заводим массив целых чисел размером с поле. Когда найден очередной вариант расстановки, инкрементим те клетки этого массива, где в найденном варианте стоят мины. В конце получим массив, показывающий суммарное число появлений мин в каждой клетке. Осталось поделить эти числа на количество вариантов - все вероятность готова, извольте кушать! Только не забудьте разложить по риал-тарелкам..

Беда только в том, что задача либо довольно долго считается (для нормальных размеров, типа 20) - так как прибавление одного поля даже в линейном варианте удваивает (кажется) количество вычислений, либо жрет памяти немеряно (мой гигабайт ушел играючи на длину массива, кажется, меньше 30). Короче, не все так просто..

[hardcase]

Ага, я подозревал, что задача про расстановки мин появилась неспроста! Вот и продолжение..

Короче идея мне ясна.
Брутфорс расстановок....
Но сдаётся мне можно и без полного перечисления. Правда, в условии сказано, что максимальный размер поля 20х20...
Можно пробовать выделять области, в которых вероятности нахождения мин равны - тогда задачка немного упрощается и брутфорсить надо только в местах, где открытые области соприкасаются с закрытыми.

Кстати про гигабайты - там было ограничение на количество памяти, кажется 64МБ.

Сообщение отредактировано: hardcase - 25.01.2006 17:24