Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / WinForms, .Net Framework |
![]() ![]() |
Ролг Хупин 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] Ответить | Цитировать Сообщить модератору |
Ролг Хупин Member Откуда: Чебаркуль Сообщений: 3263 |
Всё, вопрос снят :-) |
11 авг 18, 15:43 [21638768] Ответить | Цитировать Сообщить модератору |
Все форумы / WinForms, .Net Framework | ![]() |