Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / WinForms, .Net Framework Новый топик    Ответить
 Помогите реализовать такую пуззле  [new]
Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 3263
Вот перевод постановки, но может кто в курсе, может в интернете есть что-то на шарпе, без юзер интерфейса?
Такие игрушки есть на смартфонах под Андроидом.

-----------
Сегодня мы собираемся реализовать популярную однопользовательскую игру, которая доступна на многих
смартфонов. Игроку дается n x n доска плиток, где каждому плитку дают один
цветов. Каждая плитка соединена с четырьмя соседними плитами в северном, южном, восточном и западном направлениях. Плитка связана с началом (плитка в верхнем левом углу), если она имеет тот же цвет, что и источник, и есть путь к началу координат, состоящий только из плиток этого цвета. Игрок делает ход, выбирая один из цветов. После того, как выбор сделан, все плитки, которые связаны с источником, меняются на выбранный цвет. Игра продолжается до тех пор, пока все плитки платы не будут иметь тот же цвет. Цель игры - изменить все плитки на один и тот же цвет, желательно с наименьшим количеством возможных движений.
Было доказано, что поиск оптимальных ходов - очень сложная вычислительная проблема. Было также показано, что поиск минимального количества операций наводнения NP-hard при m> 3. Это даже верно, когда игрок может выполнять операции затопления из любой позиции на доске. Однако этот вариант можно решить в полиномиальное время для частного случая m = 2. Для неограниченного количества цветов даже этот вариант остается NP-твердым для досок размером не менее n = 3 и разрешимо в полиномиальное время для плат размером n = 2.
Для вашего решения вы реализуете очень простую жадную стратегию для ее решения:
 для каждого хода выберите цвет, который приведет к наибольшему количеству плиток
 подключен к источнику;
 если есть галстук, сломайте связи, выбрав цвет, который имеет самый низкий ранг среди цветов.
На следующем рисунке показана возможная последовательность движений вместе с выбранным цветом на панели 6 x 6, первоначально заполненной тремя различными цветами.
Внесите в игру и автоматизированного игрока, который определяет выбор цвета для каждого хода. Мы хотим определить количество ходов и последовательность цветов, выбранных игроком в течение игры. Пожалуйста, используйте модульные тесты, чтобы убедиться, что ваш код работает правильно! Нет необходимости внедрять какой-либо пользовательский интерфейс, просто используйте свой модульный тест в качестве драйвера вашего программного обеспечения.
Если вы можете быстро реализовать простой жадный алгоритм, вы можете предложить улучшенное решение с использованием модифицированного алгоритма A *.
---------
11 авг 18, 11:18    [21638611]     Ответить | Цитировать Сообщить модератору
 Re: Помогите реализовать такую пуззле  [new]
Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 3263
Всё, вопрос снят :-)
11 авг 18, 15:43    [21638768]     Ответить | Цитировать Сообщить модератору
Все форумы / WinForms, .Net Framework Ответить