![]() |
| | |||||||
| Регистрация | Правила | Блоги | Пользователи | Социальные группы | Поиск | Сообщения за день | Все разделы прочитаны |
| |
![]() |
| |
| | #1 | |
| BadBaddak Новичок Регистрация: 09.06.2010
Сообщений: 85 Репутация: 59 (2) |
В инете есть много флеш игр на тему вирусов. Поле поделено на квадраты из нескольких цветов и нужно всё заразить на наименьшее число ходов. Хочу потренироваться находить решения таких задач. Для примера возьмём "Перекрась поле!". Поле 14*14 клеток, 6 разных цветов, главная клетка - верхняя левая, дают 30 ходов. Поле в программу вбивать пока придётся в ручную. С чего начать создание решалки? Алгоритм дума сделать полным перебором, как просчитываются перекрашивания? Наверное придётся вводить 6 чисел для обычных клеток + 6 для вирусных. Поле лучше делать в виде чисел в массиве, или символов в строках? | |
| | ||
| Другие темы раздела | |
| C++ Multyplayer Game Server Здравствуйте, захотелось для общего развития написать игрушку реального времени, но для этого надо иметь сервер. Можно написать все это самому, но охота узнать есть ли какие готовые продукты какими все пользуются, что-бы можно было использовать выбранную платформу в дальнейшем а не каждый раз.... Multyplayer Game Server | Критика архитектуры набора планов C++ Требуется создать систему похожую на Hierarchical task network то есть некоторая библиотека планов и каждый план может содержать подпланы, получать результаты выполнения подпланов и передавать их в другие подпланы используется в системе управления ботами в командной реалтайм игре. пока мои.... Критика архитектуры набора планов |
| | #11 | ||||||
| voral Форумчанин Регистрация: 16.03.2008 Адрес: Иваново
Сообщений: 594 Репутация: 113 (101) | У тебя файл содержит все поле. Т.е. выглядит как массив (один символ на ячйку). Н у так все просто:
1 обработать ситуацию когда символов в строке или количество строк отличается от размеров массива. 2 обработать ситуацию, когда среди всех окажется "чужеродный сивол" (например испоьзуете только три цвета R, G и B..... Массив должен содержать только их, но вдруг там еще Х) | ||||||
| | |||||||
| | #12 | |||||||||||
| BadBaddak Новичок Регистрация: 09.06.2010
Сообщений: 85 Репутация: 59 (2) |
Разобрался немного. (Про getchar() не знал, в учебнике по строкам работают) До 29 строки не дойдёт, потому что у меня из цикла выход через ретурн стоит. Файл надо переоткрыть, чтоб строки читались с начала. Процедура будет заполнять массив A и сразу показывает исходное положение на поле:
Сделаю ещё один массив для букв-цветов. Полный перебор по полю поможет определить сколько и какие буквы там есть. Это сделаю. Думаю как лучше организовать перебор всех вариантов? Есть может у кого пример? Если 6 цветов, попробуем перебрать 10 ходов, то всего 6*5*5*5*5*5*5*5*5*5=50.4 миллиона вариантов многа...Добавлено через 22 часа 49 минут Эта процедура смотрит какие цвета есть на поле, и делает их них массив. Кроме того показывает их на консоли. Вроде работает правильно.
Последний раз редактировалось BadBaddak; 23.07.2011 в 01:18. Причина: getchar() | |||||||||||
| | ||||||||||||
| | #13 | ||||||
| BadBaddak Новичок Регистрация: 09.06.2010
Сообщений: 85 Репутация: 59 (2) |
Но это ручное заражение на основании ближайших клеток. Может сделать не "больше клеток заразить" а какое-нибудь другое условие? | ||||||
| | |||||||
| | #14 | |
| taras atavin Нарушитель Регистрация: 24.11.2009 Адрес: Где то в сетке
Сообщений: 11,931 Репутация: 1080 (736) |
Я предлагаю перебор на всю глубину в 30 ходов.
| |
| | ||
| | #15 | |
| iama Серая масса Эксперт C++ Регистрация: 30.07.2010 Адрес: 0xDEADBEEF
Сообщений: 3,444 Репутация: 1008 (757) | taras atavin, асимптотика решения - O(C^M), где C - колличество цветов, M - колличество ходов. Для 6 цветов и 30 ходов будет работать около недели, если красивое решение будет, с малыми константами, скрытыми в асимптотике. У вас в статусе все верно написано.
| |
| | ||
| | #16 | |
| BadBaddak Новичок Регистрация: 09.06.2010
Сообщений: 85 Репутация: 59 (2) |
ухх... пошел по пути лёгкого кода ![]() Простой генератор случайных чисел RandCol=rand()%numcolor;, выбирается один из цветов. Если заражения не происходит, то цвет перевыбирается. Успешно заражаемые цвета постепенно скидываются в массив ходов, счётчик++, цикл повторяется пока всё не заразим. Если текущий проход завершился за меньшее количество ходов, чем предыдущие, то выводим массив последовательности на консоль. Пока мыл посуду, комп нашел вариант с 20 ходами. Обратите внимание, что цвет Y заражает одним разом 27 клеток. (не говорите про HODOV, сам знаю )
| |
| | ||
| | #17 | |
| BadBaddak Новичок Регистрация: 09.06.2010
Сообщений: 85 Репутация: 59 (2) |
Сделал оптимизацию: если при переборе найдено минимальное число ходов, оно запоминается. Если следующее заражение идёт за бОльшее число ходов, оно не просчитывается до конца, а пропускается. На скрине видно, что за 9 секунд просчитало 66 тысяч вариантов. Прога сканирует цвета на экране, заносит поле в массив, просчитывает на минимально возможное число ходов рандомным перебором, каждое найденное решение пишется поверх старого. Вручную заражаю тот цвет, который первый в строке, поле перекрашивается, перезапускаю скнирование и т.д. После решения последнего десятого уровня у меня стало больше 10 миллионов очков. Игра решена и пройдена! | |
| | ||
| После регистрации реклама в сообщениях будет скрыта | |
| | #18 | |
| talis Форумчанин Регистрация: 11.05.2010 Адрес: talis_t * ptr = &talis;
Сообщений: 1,186 Репутация: 675 (482) | BadBaddak, в качестве оптимизации: если проц многоядерный, посмотрите в сторону поиска решения в нескольких параллельных потоках. Да, и вместо копирования массива в цикле поэлементно, попробуйте через memcpy() :-) | |
| | ||
![]() |
| Похожие темы | |
| Тема | Автор |
| C# для начинающих Реализация Игры "Жизнь" из книги Уэзерелл Ч. "Этюды для программистов" Кто нибудь встречал ее нга с#??? Если у кого-то есть, вы не могли бы выложить исходник? | demon_666_902 |
| C# для начинающих Игра "Змейка", ошибка "Globals.Close не объявлен", неправильная логика игры Нашёл в интернете код игры "змейка" и саму скомпилированную игру. Но есть загвоздка. А точнее две using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; using... | Ney4 |
| Pascal (Паскаль) Решение заданий типа "Array","Matrix","String","File","Text""" большая просьба помочь решить где-то около 35-40 (из 100) задач (мне не понятных) типа массив и матрица я буду рад (да и если у кого будет желание) если кто нибудь будет давать еще пояснения к задача необязательно но желательно. сам я уже перегрузился от этих задач уже торможу (Меня девушка уже... | tork113 |
| Turbo Pascal из слова "вирус" путем замены его букв получить слово "фокус" из слова "вирус" путем замены его букв получить слово "фокус" | Возбуждающая |
| C++ Builder Создание игры "монополия" или по-другому "менеджер" Доброго всем дня, задача ставится, написать игру с возможностями OpenGL, дабы создать красочное меню и анимацию, игра подразумевает работа с сетью(но это решабельный вопрос, будут использоваться компоненты TServerSocket и TClientSocket, с ними все понятно), игра будет по сети. Чтобы я хотел узнать... | GaFBich |
| Опции темы | |
| |
| |