Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.65/20: Рейтинг темы: голосов - 20, средняя оценка - 4.65
90 / 17 / 4
Регистрация: 09.06.2010
Сообщений: 100
1

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

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

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

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

Ошибка: invalid conversion from "int" to "SDL_RendererFlip"
Скриншот приложен, Вот страница, откуда я брал этот код Подскажите что делать

О "нестабильности" или "переполнении" цикла foreach
Здравствуйте, коллеги. Недавно коллега-программист сообщил мне страшную вещь: оказывается, что...

CString buff = "aaa" + "bbb"
Хочется одним оператором конкатенировать несколько подстрок CString buff = "aaa" + "bbb"...

18
1334 / 985 / 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
Название: 2011-07-17_182925.png
Просмотров: 162

Размер: 19.5 Кб
Здесь точками выделены уже зараженные клетки (в некоторых играх точки не ставят). Сейчас можно заразить оранжевый цвет. Все старые вирусные клетки станут оранжевыми + захватятся 11 оранжевых клеток которые касаются вируса. Следующим ходом можно заразить синий цвет и т.д. По диагонали клетки не заражаются.
0
Jesus loves me
Эксперт С++
5096 / 3110 / 351
Регистрация: 12.12.2009
Сообщений: 7,853
Записей в блоге: 2
17.07.2011, 18:37 4
Считаешь кол-во всех прилегающих клеток разных цветов, каких цветов больше - того цвета будет следующий ход. Поскольку поле небольшое, можно сделать через GetPixel(), значениями, которые она вернет, заполнять массив 16*16. Ну а дальше все просто))
0
90 / 17 / 4
Регистрация: 09.06.2010
Сообщений: 100
17.07.2011, 23:10  [ТС] 5
Как раз правильный ход может быть не тот, где много клеток (особенно в конце). Главное заползти подальше в глубь, потому что так больше будет захватываться в других ходах. В общем начнём с поля и быстренького анализа, определение соседних цветов, и потренироваться в захвате вирусякой соседних.
Это пример на котором буду тренироваться
Решение игры "вирус"?
0
1334 / 985 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
17.07.2011, 23:56 6
Ну в принципе, для большого поля это - довольно сложная задача динамического программирования, а для 16х16 можете тупой перебор написать, должно работать нормально
0
1195 / 822 / 180
Регистрация: 16.03.2008
Сообщений: 3,950
Записей в блоге: 1
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 желтый
Теперь смотрим букву вируса (верхняя левая - буква r), меняем её в массиве на * , теперь из перебора ищем допустимые ходы. Так? В первом ходе только голубой, на второй ход возможны жёлтый, розовый, фиолетовый. При захвате розового нужно будет захватить уголок на 3 клеточки в правую сторону.
0
1334 / 985 / 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
Пока такой кусок. Подскажите, как лучше из отдельных строк делать один массив байт?
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;
}
0
1195 / 822 / 180
Регистрация: 16.03.2008
Сообщений: 3,950
Записей в блоге: 1
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..... Массив должен содержать только их, но вдруг там еще Х)
0
90 / 17 / 4
Регистрация: 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]);
    }
}
0
90 / 17 / 4
Регистрация: 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 переписывается в массив А. Всё повторяется.
Но это ручное заражение на основании ближайших клеток. Может сделать не "больше клеток заразить" а какое-нибудь другое условие?
0
Миниатюры
Решение игры "вирус"?  
4194 / 1787 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
07.02.2012, 11:02 14
Я предлагаю перебор на всю глубину в 30 ходов.
0
1334 / 985 / 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
Миниатюры
Решение игры "вирус"?  
794 / 546 / 61
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
27.03.2012, 10:16 18
BadBaddak, в качестве оптимизации: если проц многоядерный, посмотрите в сторону поиска решения в нескольких параллельных потоках.

Да, и вместо копирования массива в цикле поэлементно, попробуйте через memcpy() :-)
0
0 / 0 / 0
Регистрация: 30.10.2016
Сообщений: 6
12.05.2017, 18:06 19
Здравствуйте, а остался исходник с игры?
И если да, можно его получить?)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.05.2017, 18:06

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Вывести фигуру, состоящую из букв "а" и "b"
Пользователем задаются параметры: h- высота фигуры, w - ширина фигуры, s - размер.Запрещено...

Qt Creator. Все "за" и "против"
Доброго времени суток, форумчане! Сегодня задался вопросом использования такой IDE, как Qt Creator....

Ошибка E0167 аргумент типа "unsigned char *" несовместим с параметром типа "const char *"
Всем привет, подскажите пожалуйста, в проекте MS Visual Studio 2017 напротив строчки...

Ищу исходник игры на С++, на подобие "Солитер", "Быки и коровы", "Змейка" и т. д
Нужен код игры на С++, на подобие &quot;Солитер&quot;, &quot;Быки и коровы&quot;, &quot;Змейка&quot; и т. д. Или ссылки на...


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

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Опции темы

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