Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.86
BadBaddak
87 / 14 / 3
Регистрация: 09.06.2010
Сообщений: 100
#1

Решение игры "вирус"? - C++

17.07.2011, 17:42. Просмотров 2726. Ответов 18
Метки нет (Все метки)

В инете есть много флеш игр на тему вирусов. Поле поделено на квадраты из нескольких цветов и нужно всё заразить на наименьшее число ходов.
Хочу потренироваться находить решения таких задач.
Для примера возьмём "Перекрась поле!". Поле 14*14 клеток, 6 разных цветов, главная клетка - верхняя левая, дают 30 ходов. Поле в программу вбивать пока придётся в ручную. С чего начать создание решалки? Алгоритм дума сделать полным перебором, как просчитываются перекрашивания? Наверное придётся вводить 6 чисел для обычных клеток + 6 для вирусных. Поле лучше делать в виде чисел в массиве, или символов в строках?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.07.2011, 17:42     Решение игры "вирус"?
Посмотрите здесь:

Необработанное исключение в "0x77913ab3" в "x": 0xC0000005: Нарушение прав доступа при чтении "0xdddddddd" - C++
вот код, нужно найти 3 минимальных положительных числа в массиве. При размере массива больше 950 в конце заполнения рандомным способом...

Перевести исходник игры "Собери картинку" c Delphi 7 на С++ Builder 6 - C++ Builder
Помогите перевести!

Создание простой игры, каким образом распределить "обязанности" - C++
В общем идея такая, на данный момент есть более-менее работающий прототип (звёздочками в консоли) "битвы алгоритмов": поочерёдно вызываются...

Есть у кого-нибудь исходник игры "Морской Бой"? - C++
Ребят, может у кого завалялся исходник "Морского Боя"?

Battleship Helper (помошник для игры "Морской бой") - C++ Builder
Идея: на каждой клетке в процентах вероятность что там корабль На данный момент: программа выдает одинаковый процент на каждую, не...

Помогите придумать 12 функций программы для игры в "Спички" - C++
Помогите придумать 12 функций программы для игры в "Спички". НА пример первая функция умственное развитие, вторая развитие логического...

Написать программу для игры "Камень, бумага, ножницы" - C++
Прочитал четыри главы книги Бьярне Страуструп Программирование: принципы и практика использования C++, исправленное издание и приступил...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
iama
1249 / 974 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
17.07.2011, 17:51     Решение игры "вирус"? #2
Выложите законы, по которым можно заражать поле
BadBaddak
87 / 14 / 3
Регистрация: 09.06.2010
Сообщений: 100
17.07.2011, 18:36  [ТС]     Решение игры "вирус"? #3
Название: 2011-07-17_182925.png
Просмотров: 151

Размер: 19.5 Кб
Здесь точками выделены уже зараженные клетки (в некоторых играх точки не ставят). Сейчас можно заразить оранжевый цвет. Все старые вирусные клетки станут оранжевыми + захватятся 11 оранжевых клеток которые касаются вируса. Следующим ходом можно заразить синий цвет и т.д. По диагонали клетки не заражаются.
Kastaneda
Форумчанин
Эксперт С++
4479 / 2841 / 226
Регистрация: 12.12.2009
Сообщений: 7,222
Записей в блоге: 1
Завершенные тесты: 1
17.07.2011, 18:37     Решение игры "вирус"? #4
Считаешь кол-во всех прилегающих клеток разных цветов, каких цветов больше - того цвета будет следующий ход. Поскольку поле небольшое, можно сделать через GetPixel(), значениями, которые она вернет, заполнять массив 16*16. Ну а дальше все просто))
BadBaddak
87 / 14 / 3
Регистрация: 09.06.2010
Сообщений: 100
17.07.2011, 23:10  [ТС]     Решение игры "вирус"? #5
Как раз правильный ход может быть не тот, где много клеток (особенно в конце). Главное заползти подальше в глубь, потому что так больше будет захватываться в других ходах. В общем начнём с поля и быстренького анализа, определение соседних цветов, и потренироваться в захвате вирусякой соседних.
Это пример на котором буду тренироваться
Решение игры "вирус"?
iama
1249 / 974 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
17.07.2011, 23:56     Решение игры "вирус"? #6
Ну в принципе, для большого поля это - довольно сложная задача динамического программирования, а для 16х16 можете тупой перебор написать, должно работать нормально
voral
409 / 389 / 51
Регистрация: 16.03.2008
Сообщений: 1,921
18.07.2011, 17:29     Решение игры "вирус"? #7
На уровне сырой мысли:
- Для каждой ячейки рассчитываем размер одноцветной группы в которую она входит.
- При движении близко к границам имеем ограничение возможностей. Т.е. со стороны границы поля если мы захватили уже о нее больше ни чего не добавляется в зараженный район - по этому лучше держаться диагонали
- Желательно выбирать те соседние регионы, размер которых больше.

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


Как дошли до противоположного угла смотрим остались ли не зараженные участки. На этих участках так же все решаем.
BadBaddak
87 / 14 / 3
Регистрация: 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 желтый
Теперь смотрим букву вируса (верхняя левая - буква r), меняем её в массиве на * , теперь из перебора ищем допустимые ходы. Так? В первом ходе только голубой, на второй ход возможны жёлтый, розовый, фиолетовый. При захвате розового нужно будет захватить уголок на 3 клеточки в правую сторону.
iama
1249 / 974 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
22.07.2011, 11:06     Решение игры "вирус"? #9
BadBaddak, переборным алгоритмом в этом случае будет генерация всех возможных последовательностей захватываемых цветов, ответом будет самая короткая из них.
BadBaddak
87 / 14 / 3
Регистрация: 09.06.2010
Сообщений: 100
23.07.2011, 00:55  [ТС]     Решение игры "вирус"? #10
Пока такой кусок. Подскажите, как лучше из отдельных строк делать один массив байт?
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // для работы со строками
 
int Stolb,Strok;
char s[]; // для чтения строк с файла
char A[30][30]; // для поля
int i, j;
FILE *fp; // указатель на файл
 
void PoleTxt()
{
    fp = fopen ( "pole.txt", "r" );
    Stolb=0;
    Strok=0;
 
// определяем высоту и ширину массива
 while (1){ // пока не кончится файл или будет пустая строка
    if ( NULL == fgets ( s, 80, fp ) ) {// если ошибка чтения
        printf ( "end file\n" );
        return(0);
    }
    else
        if (strlen(s)==1) return(0); // пустрая строка равна единице!!
        if (Stolb==0) Stolb = strlen(s)-1; // букв в строчке
        Strok ++;
 }
 // здесь надо перегнать из файла в массив A[][] Как?
    fclose ( fp );
}
 
void ShowPole() // печатает поле на консоли, массив не заполнил
{
    for ( i = 0; i < Stolb; i ++ ){
        for ( j = 0; j < Strok; j ++ ){
            printf ( "%2c", A[i][j] );
        }
        printf("\n");
    }
}
 
int main()
{
 
    PoleTxt(); // читаем массив из файла
    printf ( "strok:   %d\n",Strok );
    printf ( "stolbov: %d\n",Stolb );
    ShowPole(); // выводим поле на консоль
    // тут другие функции
    return 0;
}
voral
409 / 389 / 51
Регистрация: 16.03.2008
Сообщений: 1,921
23.07.2011, 01:14     Решение игры "вирус"? #11
Цитата Сообщение от BadBaddak Посмотреть сообщение
Пока такой кусок. Подскажите, как лучше из отдельных строк делать один массив байт?
У тебя файл содержит все поле. Т.е. выглядит как массив (один символ на ячйку). Н у так все просто:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
freopen("game.dat", "r", stdin);
char c;
int i=0;
int j=0;
while (c=getchar())!=EOF)
{
    if (c=="\n")
   {
     ++i;
     j=0;
   }
   else 
  {
    A[i][j]=c;
    ++j;
  }
}
Вот такая заготовка. Только обязательно нужно:
1 обработать ситуацию когда символов в строке или количество строк отличается от размеров массива.
2 обработать ситуацию, когда среди всех окажется "чужеродный сивол" (например испоьзуете только три цвета R, G и B..... Массив должен содержать только их, но вдруг там еще Х)
BadBaddak
87 / 14 / 3
Регистрация: 09.06.2010
Сообщений: 100
24.07.2011, 18:38  [ТС]     Решение игры "вирус"? #12
Разобрался немного. (Про getchar() не знал, в учебнике по строкам работают)
До 29 строки не дойдёт, потому что у меня из цикла выход через ретурн стоит. Файл надо переоткрыть, чтоб строки читались с начала. Процедура будет заполнять массив A и сразу показывает исходное положение на поле:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void ShowPole()
{
    fp = fopen ( "pole.txt", "r" );
    // из файла заполняем массив по буквенно
    for (i=0; i<Strok; i++) {
        fgets ( s, 80, fp ); 
        for (j=0; j<Stolb; j++){
            A[i][j]=s[j]; // побуквенно заполняем массив
        }
    }
 
    //вывод массива в консоль
    for ( i = 0; i < Stolb; i ++ ){
        for ( j = 0; j < Strok; j ++ ){
            printf ( "%2c", A[i][j] );
        }
        printf("\n");
    }
 
    fclose ( fp );
}
Добавлено через 18 часов 34 минуты
Сделаю ещё один массив для букв-цветов. Полный перебор по полю поможет определить сколько и какие буквы там есть. Это сделаю. Думаю как лучше организовать перебор всех вариантов? Есть может у кого пример? Если 6 цветов, попробуем перебрать 10 ходов, то всего 6*5*5*5*5*5*5*5*5*5=50.4 миллиона вариантов многа...

Добавлено через 22 часа 49 минут
Эта процедура смотрит какие цвета есть на поле, и делает их них массив. Кроме того показывает их на консоли. Вроде работает правильно.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void SetColor()
{
    //перебор массива и заполнение цветов
    for (k=0; k<10; k++) color[k]=0; // обнуляем
 
    for ( i = 0; i < Stolb; i ++ ){
        for ( j = 0; j < Strok; j ++ ){
            for (k=0; k<10; k++){ // перебор массива цветов
                if (color[k]==0) { // если ноль, пишем новый цвет
                    color[k]=A[i][j];
                    break; // выход на след клетку поля
                }
                if (color[k]==A[i][j]) { // если та же буква, то след буква
                    break;
                }
            }
        }
     }
     // сколько цветов
    for (k=0; k<10; k++){
        if (color[k]!=0) numcolor++;
    }
    printf ("vsego tsvetov: %d \n",numcolor);
 
    // вывод массива цветов
    for (k=0; k<numcolor; k++){
        printf ("%d %c \n",k+1,color[k]);
    }
}
BadBaddak
87 / 14 / 3
Регистрация: 09.06.2010
Сообщений: 100
03.02.2012, 14:38  [ТС]     Решение игры "вирус"? #13
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
int zaragenie(char ColorVir)
{
    // перебор поля, чтобы определить сколько клеток можно заразить
    // дублируем с массива A на изменяемый B
    for ( i = 0; i < Strok; i ++ ){
        for ( j = 0; j < Stolb; j ++ ){
            B[i][j]=A[i][j];
        }
     }
 
     int flag=0;
     skolkozarazaem=0;
     while (flag==0) // хотя бы одна заразилась
     {
         for ( i = 0; i < Strok; i ++ )
         {
            for ( j = 0; j < Stolb; j ++ )
            {
                // заражаем соседние клетки
                if (B[i][j]=='.') {
                   
                    // заражаем клетку СНИЗУ
                    if (i<Strok && B[i+1][j]==ColorVir){
                        B[i+1][j]='.';
                        skolkozarazaem++;
                        flag=1;
                    }
 
                    // заражаем клетку СВЕРХУ
                    if (i>0 && B[i-1][j]==ColorVir){
                        B[i-1][j]='.';
                        skolkozarazaem++;
                        flag=1;
                    }
 
                    // заражаем клетку СПРАВА
                    if (j<Stolb && B[i][j+1]==ColorVir){
                        B[i][j+1]='.';
                        skolkozarazaem++;
                        flag=1;
                    }
 
                    // заражаем клетку СЛЕВА
                    if (j>0 && B[i][j-1]==ColorVir){
                        B[i][j-1]='.';
                        skolkozarazaem++;
                        flag=1;
                    }
                }
            }
         }
         if (flag==0) return skolkozarazaem;
         flag=0;
     }
}
Вот функция заражения. В неё передаётся цвет вируса, возвращается количество заражаемых клеток. Глядя на экран человек выбирает какой именно цвет надо заразить, происходит заражение и массив B переписывается в массив А. Всё повторяется.
Но это ручное заражение на основании ближайших клеток. Может сделать не "больше клеток заразить" а какое-нибудь другое условие?
Миниатюры
Решение игры "вирус"?  
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.02.2012, 11:02     Решение игры "вирус"? #14
Я предлагаю перебор на всю глубину в 30 ходов.
iama
1249 / 974 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
08.02.2012, 13:38     Решение игры "вирус"? #15
taras atavin, асимптотика решения - O(C^M), где C - колличество цветов, M - колличество ходов. Для 6 цветов и 30 ходов будет работать около недели, если красивое решение будет, с малыми константами, скрытыми в асимптотике. У вас в статусе все верно написано.
BadBaddak
87 / 14 / 3
Регистрация: 09.06.2010
Сообщений: 100
17.02.2012, 04:12  [ТС]     Решение игры "вирус"? #16
ухх... пошел по пути лёгкого кода
Простой генератор случайных чисел RandCol=rand()%numcolor;, выбирается один из цветов. Если заражения не происходит, то цвет перевыбирается. Успешно заражаемые цвета постепенно скидываются в массив ходов, счётчик++, цикл повторяется пока всё не заразим.
Если текущий проход завершился за меньшее количество ходов, чем предыдущие, то выводим массив последовательности на консоль.
Пока мыл посуду, комп нашел вариант с 20 ходами. Обратите внимание, что цвет Y заражает одним разом 27 клеток. (не говорите про HODOV, сам знаю )
Миниатюры
Решение игры "вирус"?   Решение игры "вирус"?  
BadBaddak
87 / 14 / 3
Регистрация: 09.06.2010
Сообщений: 100
24.02.2012, 03:56  [ТС]     Решение игры "вирус"? #17
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Сделал оптимизацию: если при переборе найдено минимальное число ходов, оно запоминается. Если следующее заражение идёт за бОльшее число ходов, оно не просчитывается до конца, а пропускается. На скрине видно, что за 9 секунд просчитало 66 тысяч вариантов.
Прога сканирует цвета на экране, заносит поле в массив, просчитывает на минимально возможное число ходов рандомным перебором, каждое найденное решение пишется поверх старого. Вручную заражаю тот цвет, который первый в строке, поле перекрашивается, перезапускаю скнирование и т.д.
После решения последнего десятого уровня у меня стало больше 10 миллионов очков. Игра решена и пройдена!
Миниатюры
Решение игры "вирус"?  
talis
791 / 543 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
27.03.2012, 10:16     Решение игры "вирус"? #18
BadBaddak, в качестве оптимизации: если проц многоядерный, посмотрите в сторону поиска решения в нескольких параллельных потоках.

Да, и вместо копирования массива в цикле поэлементно, попробуйте через memcpy() :-)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.05.2017, 18:06     Решение игры "вирус"?
Еще ссылки по теме:

Идеи алгоритма для решения игры "Snake" - C++
Доброй ночи форумчане, прежде всего спасибо всем модераторам и участникам дискуссий за этот форум, уже около года я черпаю отсюда...

Ошибки "multiple definition" при компиляции игры - C++
Здравствуйте, в общем в прошлой теме rikimaru2013 дал мне почти весь код и я его доделывал, но у меня что-то не получилось и ошибки...

Поиск алгоритма для реализации игры "Покер" - Visual C++
И так задача следующая : нужно написать игру покер (Техасский холдем) для win32 console application. Многие из Вас наверно знакомы с...

Таблица рекордов для игры "Угадай число" - C++ Builder
Здравствуйте. Передо мною стоит задача: сделать в С++ Builder 6 игру &quot;Угадай число&quot;. Справился со всем, кроме таблицы рекордов. Нужно...

Создание программы наподобие игры "кто хочет стать миллионером" - C++
А возможно ли создать программу которая например выдает вопрос из 100 рандомно и 4 варианта ответа с считывает их и считает кол-во ответов...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
bodya_nik13
0 / 0 / 0
Регистрация: 30.10.2016
Сообщений: 6
12.05.2017, 18:06     Решение игры "вирус"? #19
Здравствуйте, а остался исходник с игры?
И если да, можно его получить?)
Yandex
Объявления
12.05.2017, 18:06     Решение игры "вирус"?
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru