90 / 17 / 4
Регистрация: 09.06.2010
Сообщений: 100
|
|
1 | |
Решение игры "вирус"?17.07.2011, 17:42. Показов 5010. Ответов 18
Метки нет (Все метки)
В инете есть много флеш игр на тему вирусов. Поле поделено на квадраты из нескольких цветов и нужно всё заразить на наименьшее число ходов.
Хочу потренироваться находить решения таких задач. Для примера возьмём "Перекрась поле!". Поле 14*14 клеток, 6 разных цветов, главная клетка - верхняя левая, дают 30 ходов. Поле в программу вбивать пока придётся в ручную. С чего начать создание решалки? Алгоритм дума сделать полным перебором, как просчитываются перекрашивания? Наверное придётся вводить 6 чисел для обычных клеток + 6 для вирусных. Поле лучше делать в виде чисел в массиве, или символов в строках?
0
|
17.07.2011, 17:42 | |
Ответы с готовыми решениями:
18
Вирус не даёт устанавливать игры! Вирус при скачивании игры Словил вирус при скачивании игры Возможно вирус при установки игры |
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
17.07.2011, 17:51 | 2 |
Выложите законы, по которым можно заражать поле
0
|
90 / 17 / 4
Регистрация: 09.06.2010
Сообщений: 100
|
|
17.07.2011, 18:36 [ТС] | 3 |
Здесь точками выделены уже зараженные клетки (в некоторых играх точки не ставят). Сейчас можно заразить оранжевый цвет. Все старые вирусные клетки станут оранжевыми + захватятся 11 оранжевых клеток которые касаются вируса. Следующим ходом можно заразить синий цвет и т.д. По диагонали клетки не заражаются.
0
|
17.07.2011, 18:37 | 4 |
Считаешь кол-во всех прилегающих клеток разных цветов, каких цветов больше - того цвета будет следующий ход. Поскольку поле небольшое, можно сделать через GetPixel(), значениями, которые она вернет, заполнять массив 16*16. Ну а дальше все просто))
0
|
90 / 17 / 4
Регистрация: 09.06.2010
Сообщений: 100
|
|
17.07.2011, 23:10 [ТС] | 5 |
Как раз правильный ход может быть не тот, где много клеток (особенно в конце). Главное заползти подальше в глубь, потому что так больше будет захватываться в других ходах. В общем начнём с поля и быстренького анализа, определение соседних цветов, и потренироваться в захвате вирусякой соседних.
Это пример на котором буду тренироваться
0
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
17.07.2011, 23:56 | 6 |
Ну в принципе, для большого поля это - довольно сложная задача динамического программирования, а для 16х16 можете тупой перебор написать, должно работать нормально
0
|
18.07.2011, 17:29 | 7 |
На уровне сырой мысли:
- Для каждой ячейки рассчитываем размер одноцветной группы в которую она входит. - При движении близко к границам имеем ограничение возможностей. Т.е. со стороны границы поля если мы захватили уже о нее больше ни чего не добавляется в зараженный район - по этому лучше держаться диагонали - Желательно выбирать те соседние регионы, размер которых больше. Таким образом рассчитываем путь до дальнего угла с таким рассчетом, чтобы пройти через все регионы большого размера лежащие в вблизи диагонали. Если до следующего "большого" региона можно пройти выбрав цвет из двух и больше, выбираем тот который имеет больше прилегающих к зараженной области ячеек. Как дошли до противоположного угла смотрим остались ли не зараженные участки. На этих участках так же все решаем.
0
|
90 / 17 / 4
Регистрация: 09.06.2010
Сообщений: 100
|
|
22.07.2011, 01:22 [ТС] | 8 |
Поле забивать решил с текст файла. Во первых, так можно записать любое поле. Во вторых, потом можно будет написать скан экрана, который сам будет создавать текстовый файл. Количество столбиков по символам, строки по строкам, кол-во цветов можно вычислить перебором, пустая строка - конец поля. Получилось примерно так:
Код
rbyprypybbpvgb bbppyyvrrvygvg vvgvvvvbrypvrr yyvpprgrbpgrpy gbybpvpbrbvvry rrygpprgbpppyy vbvbbpbprryvgr gvpgrvbvgprvpr vbpgbygvryrvrb ggpgrprvpbvpgb gppvbbybbbpbrp bbybbrgygrrrvy rpgygypbryybgr gpyrbbvrbvgvrv r red красный v violet фиолетовый p pink розовый g green зеленый b blue голубой y yellow желтый
0
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
22.07.2011, 11:06 | 9 |
BadBaddak, переборным алгоритмом в этом случае будет генерация всех возможных последовательностей захватываемых цветов, ответом будет самая короткая из них.
0
|
90 / 17 / 4
Регистрация: 09.06.2010
Сообщений: 100
|
||||||
23.07.2011, 00:55 [ТС] | 10 | |||||
Пока такой кусок. Подскажите, как лучше из отдельных строк делать один массив байт?
0
|
23.07.2011, 01:14 | 11 | |||||
У тебя файл содержит все поле. Т.е. выглядит как массив (один символ на ячйку). Н у так все просто:
1 обработать ситуацию когда символов в строке или количество строк отличается от размеров массива. 2 обработать ситуацию, когда среди всех окажется "чужеродный сивол" (например испоьзуете только три цвета R, G и B..... Массив должен содержать только их, но вдруг там еще Х)
0
|
90 / 17 / 4
Регистрация: 09.06.2010
Сообщений: 100
|
|||||||||||
24.07.2011, 18:38 [ТС] | 12 | ||||||||||
Разобрался немного. (Про getchar() не знал, в учебнике по строкам работают)
До 29 строки не дойдёт, потому что у меня из цикла выход через ретурн стоит. Файл надо переоткрыть, чтоб строки читались с начала. Процедура будет заполнять массив A и сразу показывает исходное положение на поле:
Сделаю ещё один массив для букв-цветов. Полный перебор по полю поможет определить сколько и какие буквы там есть. Это сделаю. Думаю как лучше организовать перебор всех вариантов? Есть может у кого пример? Если 6 цветов, попробуем перебрать 10 ходов, то всего 6*5*5*5*5*5*5*5*5*5=50.4 миллиона вариантов многа... Добавлено через 22 часа 49 минут Эта процедура смотрит какие цвета есть на поле, и делает их них массив. Кроме того показывает их на консоли. Вроде работает правильно.
0
|
90 / 17 / 4
Регистрация: 09.06.2010
Сообщений: 100
|
||||||
03.02.2012, 14:38 [ТС] | 13 | |||||
Но это ручное заражение на основании ближайших клеток. Может сделать не "больше клеток заразить" а какое-нибудь другое условие?
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
07.02.2012, 11:02 | 14 |
Я предлагаю перебор на всю глубину в 30 ходов.
0
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
08.02.2012, 13:38 | 15 |
taras atavin, асимптотика решения - O(C^M), где C - колличество цветов, M - колличество ходов. Для 6 цветов и 30 ходов будет работать около недели, если красивое решение будет, с малыми константами, скрытыми в асимптотике. У вас в статусе все верно написано.
0
|
90 / 17 / 4
Регистрация: 09.06.2010
Сообщений: 100
|
|
17.02.2012, 04:12 [ТС] | 16 |
ухх... пошел по пути лёгкого кода
Простой генератор случайных чисел RandCol=rand()%numcolor;, выбирается один из цветов. Если заражения не происходит, то цвет перевыбирается. Успешно заражаемые цвета постепенно скидываются в массив ходов, счётчик++, цикл повторяется пока всё не заразим. Если текущий проход завершился за меньшее количество ходов, чем предыдущие, то выводим массив последовательности на консоль. Пока мыл посуду, комп нашел вариант с 20 ходами. Обратите внимание, что цвет Y заражает одним разом 27 клеток. (не говорите про HODOV, сам знаю )
0
|
90 / 17 / 4
Регистрация: 09.06.2010
Сообщений: 100
|
|
24.02.2012, 03:56 [ТС] | 17 |
Сообщение было отмечено как решение
Решение
Сделал оптимизацию: если при переборе найдено минимальное число ходов, оно запоминается. Если следующее заражение идёт за бОльшее число ходов, оно не просчитывается до конца, а пропускается. На скрине видно, что за 9 секунд просчитало 66 тысяч вариантов.
Прога сканирует цвета на экране, заносит поле в массив, просчитывает на минимально возможное число ходов рандомным перебором, каждое найденное решение пишется поверх старого. Вручную заражаю тот цвет, который первый в строке, поле перекрашивается, перезапускаю скнирование и т.д. После решения последнего десятого уровня у меня стало больше 10 миллионов очков. Игра решена и пройдена!
0
|
27.03.2012, 10:16 | 18 |
BadBaddak, в качестве оптимизации: если проц многоядерный, посмотрите в сторону поиска решения в нескольких параллельных потоках.
Да, и вместо копирования массива в цикле поэлементно, попробуйте через memcpy() :-)
0
|
0 / 0 / 0
Регистрация: 30.10.2016
Сообщений: 6
|
|
12.05.2017, 18:06 | 19 |
Здравствуйте, а остался исходник с игры?
И если да, можно его получить?)
0
|
12.05.2017, 18:06 | |
12.05.2017, 18:06 | |
Помогаю со студенческими работами здесь
19
Вирус не даёт запускать антивирусы,запускает IE с рекламой игры Вирус, который устанавиливает программы левые и какие-то игры Оо Вирус! Требуеться решение! Вирус (появление рекламы) в браузерах после установки патча для игры Словил вирус при скачивании игры. Время от времени вылетают вкладки с рекламой Найти решение игры Решение игры в условиях неопределённости Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |