Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 27.11.2006, 03:58
Аватар для CAHEK_p
Новичок

Отправить личное сообщение для CAHEK_p Посмотреть профиль Найти все сообщения от CAHEK_p
 
Регистрация: 27.11.2006
Сообщений: 3

"перевертыши"
Народ!!! Помогите, пожалуйста! Сколько бы я ни мучился, никак не могу решить эту задачку! Как ее решать? Каким способом?
Самое главное, и в Интернете даже решение этой задачи нет!!!
================================================== =======

Поле для игры «Перевертыши» представляет собой прямоугольную доску, расчерченную на NxM квадратов. На каждом квадрате есть кнопка и лампочка. Лампочка может светиться одним из трех цветов: красным, зеленым или синим. При нажатии на кнопку, расположенную на какой-либо клетке, меняется цвет лампочки в этой клетке и во всех клетках, имеющих с данной общую сторону. Смена цвета лампочек всегда осуществляется по правилу: красный меняется на зеленый, зеленый на синий, а синий на красный.

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

Требуется написать программу, которая находит это наименьшее количество нажатий кнопок, обеспечивающее победу в этой игре.

Технические требования:

Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на каждый тест

Формат входных данных:

В первой строке входного файла INPUT.TXT содержатся разделенных пробелом два натуральных числа - N и М (1 <= N, М <= 10), где N - количество строк на доске, а М -количество столбцов. Далее в N строках содержится описание начального состояния поля, где каждая i-ая строка представляет собой последовательность символов, задающих цвета лампочек на соответствующей строке игрового поля. Символ «R» обозначает красный цвет, «G» — зеленый, а «В» - синий.

Формат выходных данных:

Выходной файл OUTPUT.TXT должен содержать единственное целое число -наименьшее количество нажатий кнопок, необходимое для того, чтобы лампочки на всем поле засветились одним цветом.

Примеры -файлов входных и выходных данных:
INPUT.TXT
5 5
BBBGG
BBBBG
BBBBB
GBBBB
GGBBB

OUTPUT.TXT
2
  #2  
Старый 30.11.2006, 19:26
Новичок

Отправить личное сообщение для EfremovAleksei Посмотреть профиль Найти все сообщения от EfremovAleksei
 
Регистрация: 30.11.2006
Сообщений: 8

откуда задача?
возможно, система линейных уравнений.
  #3  
Старый 02.12.2006, 11:06
Новичок

Отправить личное сообщение для Gribok Посмотреть профиль Найти все сообщения от Gribok
 
Регистрация: 26.09.2006
Сообщений: 23

Сообщение от CAHEK_p Посмотреть сообщение
Народ!!! Помогите, пожалуйста! Сколько бы я ни мучился, никак не могу решить эту задачку! Как ее решать? Каким способом?
Полный перебор по количеству нажатий первого ряда (3^10). Количество нажатий в остальных рядах вычисляются однозначно в зависимоти от выбранного цвета. В итого получам 3(цвет)3^10(первай ряд)*9*10. Должно прокатить.
  #4  
Старый 08.12.2006, 03:14
Аватар для CAHEK_p
Новичок

Отправить личное сообщение для CAHEK_p Посмотреть профиль Найти все сообщения от CAHEK_p
 
Регистрация: 27.11.2006
Сообщений: 3

> откуда задача?
задача с областной олимпиады 2004-2005г.

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
задача "быки и коровы" незарегистрированный Оффтопик 3 07.06.2008 16:59
максимальный поток\ "задача о ресурсах" ExPerT Реализация, исходники, языки 0 27.03.2007 14:08
"очень" простые циклы cmd Графы 0 10.12.2006 00:38
задача "путь к пьяной берлоге" с гранпри сибири. Ajdyn Задачи 3 18.11.2006 10:16
просьба создать раздел форума с названием "графы" CD_Eater Замечания о работе сайта 1 22.09.2006 10:56