Форум программистов, компьютерный форум, киберфорум
Наши страницы

C++

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

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

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

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

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

Найти в строке последовательность символов ("abcd") и заменить ее другой ("xyz") - C++
Найти в строке последовательность символов ("abcd") и заменить ее другой ("xyz").

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

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

CString buff = "aaa" + "bbb" - C++
Хочется одним оператором конкатенировать несколько подстрок CString buff = "aaa" + "bbb" компилятор выдает error C2110: cannot add two...

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

18
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
17.07.2011, 17:51 #2
Выложите законы, по которым можно заражать поле
0
BadBaddak
89 / 16 / 3
Регистрация: 09.06.2010
Сообщений: 100
17.07.2011, 18:36  [ТС] #3
Название: 2011-07-17_182925.png
Просмотров: 154

Размер: 19.5 Кб
Здесь точками выделены уже зараженные клетки (в некоторых играх точки не ставят). Сейчас можно заразить оранжевый цвет. Все старые вирусные клетки станут оранжевыми + захватятся 11 оранжевых клеток которые касаются вируса. Следующим ходом можно заразить синий цвет и т.д. По диагонали клетки не заражаются.
0
Kastaneda
Jesus loves me
Эксперт С++
4697 / 2901 / 238
Регистрация: 12.12.2009
Сообщений: 7,385
Записей в блоге: 2
Завершенные тесты: 1
17.07.2011, 18:37 #4
Считаешь кол-во всех прилегающих клеток разных цветов, каких цветов больше - того цвета будет следующий ход. Поскольку поле небольшое, можно сделать через GetPixel(), значениями, которые она вернет, заполнять массив 16*16. Ну а дальше все просто))
0
BadBaddak
89 / 16 / 3
Регистрация: 09.06.2010
Сообщений: 100
17.07.2011, 23:10  [ТС] #5
Как раз правильный ход может быть не тот, где много клеток (особенно в конце). Главное заползти подальше в глубь, потому что так больше будет захватываться в других ходах. В общем начнём с поля и быстренького анализа, определение соседних цветов, и потренироваться в захвате вирусякой соседних.
Это пример на котором буду тренироваться
Решение игры "вирус"?
0
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
17.07.2011, 23:56 #6
Ну в принципе, для большого поля это - довольно сложная задача динамического программирования, а для 16х16 можете тупой перебор написать, должно работать нормально
0
voral
494 / 474 / 82
Регистрация: 16.03.2008
Сообщений: 2,242
18.07.2011, 17:29 #7
На уровне сырой мысли:
- Для каждой ячейки рассчитываем размер одноцветной группы в которую она входит.
- При движении близко к границам имеем ограничение возможностей. Т.е. со стороны границы поля если мы захватили уже о нее больше ни чего не добавляется в зараженный район - по этому лучше держаться диагонали
- Желательно выбирать те соседние регионы, размер которых больше.

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


Как дошли до противоположного угла смотрим остались ли не зараженные участки. На этих участках так же все решаем.
0
BadBaddak
89 / 16 / 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 клеточки в правую сторону.
0
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
22.07.2011, 11:06 #9
BadBaddak, переборным алгоритмом в этом случае будет генерация всех возможных последовательностей захватываемых цветов, ответом будет самая короткая из них.
0
BadBaddak
89 / 16 / 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;
}
0
voral
494 / 474 / 82
Регистрация: 16.03.2008
Сообщений: 2,242
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
BadBaddak
89 / 16 / 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]);
    }
}
0
BadBaddak
89 / 16 / 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 переписывается в массив А. Всё повторяется.
Но это ручное заражение на основании ближайших клеток. Может сделать не "больше клеток заразить" а какое-нибудь другое условие?
0
Миниатюры
Решение игры "вирус"?  
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
07.02.2012, 11:02 #14
Я предлагаю перебор на всю глубину в 30 ходов.
0
iama
1251 / 976 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
08.02.2012, 13:38 #15
taras atavin, асимптотика решения - O(C^M), где C - колличество цветов, M - колличество ходов. Для 6 цветов и 30 ходов будет работать около недели, если красивое решение будет, с малыми константами, скрытыми в асимптотике. У вас в статусе все верно написано.
0
08.02.2012, 13:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2012, 13:38
Привет! Вот еще темы с ответами:

Ординарная Сеть Петри для задачи об "обедающих философах" - C++
Помогите с сетью Петри. дуб в этом Задача об обедающих философах. Пять философов отдыхают в пансионате. Каждый из философов может...

Warning LNK4248: неразрешенная лексема TypeRef для "GLUquadric" - C++
Добрый день господа эксперты! Помогите с таким вопросом компилятор выдает: frmMain.obj : warning LNK4248: неразрешенная лексема...

Ответы к упражнениям из книги Сэджвика "Фундаментальные алгоритмы на С++" части 1-4 - C++
Привет! Читаю данную книгу, в конце каждой главы имеются упражнения, но нет ответов на них. На решение некоторых задач просто нехватает...

Ошибка "неопределенная ссылка" при работе с std::thread - C++
При попытке сделать что-либо с std::thread, выдает ошибку компиляции, &quot;неопределенная ссылка &quot; . К примеру: #include...


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

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

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