С++ Помогите с задачей, перебрать все варианты

[agrizokh]

Еще один нубский вопрос. Есть задача:
Есть стена из н*н кирпичей, одни из которых желтые, другие белые. У рабочего кривая кисточка, и когда он красит один кирпич, то кирпичи сверху, снизу, справа и слева меняют свой цвет. Надо найти минимальное количество кирпичей, которые необходимо покрасить, чтобы закрасить всю стену.
Ввод:
количество стен
размер стены
сама стена

ПРИМЕР
2
3
yyy
yyy
yyy
5
wwwww
wwwww
wwwww
wwwww
wwwww

Вывод:
число кирпичей построчно, если нет вариантов - то 'inf'

Вот что я смог выдать пока, что, собственно, почти ничего:

#include<iostream>
#include<string>
using namespace std;

void paint(char arr[15][15], int x, int y)
{
   arr[x][y] = 1-arr[x][y];
   arr[x-1][y] = 1-arr[x-1][y];
   arr[x+1][y] = 1-arr[x+1][y];
   arr[x][y-1] = 1-arr[x-1][y];
   arr[x][y+1] = 1-arr[x-1][y];
}
   
int main()
{
   int n, size; 
   char pict[15][15];
   int i, j;
   cin>>n;
   
   while(n--)//big loop
   {
      cin>>size;

      for (i=0; i<size; i++)//grid input, substituting y and w for 1 and 0
         for (j=0; j<size; j++)
         {
            cin>>pict[i][j];
            if (pict[i][j]=='y')
               pict[i][j] = 1;
            else pict[i][j] = 0;
         }
      
      for(i=0; i<size; i++)
      {
         if(pict[0][i]==0)
            paint(pict, 0, i);

   }
   return 0;
}

Проблема в последнем недописанном цикле - не знаю, как его дописывать =). С логикой вроде разобрался - проэнумерировать (?) первую строчку, перебрать все возможные варианты - а остальные сделать, основываясь на первой. Только как это выполнить программно - не понимаю. Техника, которую проходили, называется Enumeration - но ввиду многозначности слова ничего достойного не нагуглил.

З.Ы. Вы уж извините, просто я учу всю эту радость на китайском - поэтому многого на лекциях по программированию не усваиваю. Приходиться как-то самому. Хорошо говорить это одно, а слушать (и понимать) на паре по с++ - это, к сожалению, другое =(
Может еще посоветуете какой хороший ресурс или книгу с разбором задач по програмированнию?

[bubu gaga]

В конце какой цвет-то у стены должен быть?

[agrizokh]

вот черт, цвет должен быть желтый

[PAV]

agrizokh в сообщении #199018 писал(а):

У рабочего кривая кисточка, и когда он красит один кирпич, то кирпичи сверху, снизу, справа и слева меняют свой цвет.

В смысле - принимают желтый цвет? Изначально желтый кирпич белым не становится?

Добавлено спустя 1 минуту 20 секунд:

Правильно ли я понимаю, что Вы изначально задали ограничение на размер стены равным 15?

"Перебрать все варианты" - это входит в условие задачи или нет?

[agrizokh]

Цитата:

В смысле - принимают желтый цвет? Изначально желтый кирпич белым не становится?

Становится. С каждой покраской цвет меняется на другой, был желтый, стал белый, если был белый, то стал желтый...

Цитата:

Правильно ли я понимаю, что Вы изначально задали ограничение на размер стены равным 15?

Да. Так есть в условии задачи.

Цитата:

"Перебрать все варианты" - это входит в условие задачи или нет?

Нет. Это уже мои домыслы. Необходимо найти МИНИМАЛЬНОЕ кол-во кирпичей.

[PAV]

Т.е. "покраска кирпича" - это такая операция, при которой он сам и все его 4 соседа меняют свои цвета на противоположные, верно?

Добавлено спустя 1 минуту 37 секунд:

Можно ли использовать рекурсию?

Добавлено спустя 2 минуты 47 секунд:

Вы знакомы с методом динамического программирования?

Добавлено спустя 1 час 17 минут 11 секунд:

Я понял, действительно, никакая рекурсия и динамическое программирование тут не требуется. При заданной раскраске первых $n$ строк раскраска следующей определяется однозначно из условия, чтобы строка $n$ состояла только из желтых кирпичей.

Я рекомендую оставить двойные массивы и работать с битовыми масками, это будет проще и в разы быстрее. Каждая строка кирпичей задается одним целым числом, каждый бит которого определяет цвет соответствующего кирпича. Другой массив целых чисел определяет, какие кирпичи мы красим. Состояние всей строки после раскраски определяется следующей операцией:

iCurColor[i] = iPrevColor[i] ^ iPaintMask[i] ^ (iPaintMask[i]<<1) ^ (iPaintMask[i]>>1) ^ iPaintMask[i-1] ^ iPaintMask[i+1]

Чтобы определить, какие кирпичи красить на очередной линии, нужно взять текущее состояние предыдущей линии и инвертировать его операцией ~. Перебор всех вариантов покраски верхней линии - это простой цикл по целым числам от 0 до (1<<n)-1. Все операции побитовые и поэтому будут выполняться очень быстро.

Вся процедура выглядит так. Нам дано начальное состояние стены. Его нужно продублировать, чтобы быстро восстанавливать после проверки каждого очередного варианта. Внешний цикл перебирает все способы раскраски верхней строки. Каждый способ применяем к стене, получая новую раскраску первой и второй строк. Затем внутренний цикл идет по строкам от 2 до последней; определяется необходимая раскраска каждой строки (инвертируя состояние предыдущей строки) и применяется к этой строке и к следующей. После окончания цикла проверяется состояние последней строки, если она полностью окрашена - тогда мы нашли очередной подходящий вариант и сравниваем его с лучшим из уже найденных. Затем восстанавливаем состояние стены к начальному виду.

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

[agrizokh]

Спасибо за советы, вроде сделал так же, но без битовых масок - и вылезает глюк, сначала всегда выводил inf (забыл упомянуть - по условию, если невозможно закрасить, должно выводить inf), а теперь вообще стопорится после ввода матрицы - не знаю, почему, продебаггил, ничего не заметил... Вот код, и вообще, правильно я написал?

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

void paint(int arr[15][15], int x, int y)
{
   arr[x][y] = 1-arr[x][y];
   arr[x-1][y] = 1-arr[x-1][y];
   arr[x+1][y] = 1-arr[x+1][y];
   arr[x][y-1] = 1-arr[x][y-1];
   arr[x][y+1] = 1-arr[x-1][y+1];
}
   
int main()
{
   int n, size, temp; 
   char input[15][15];
   int savepic[15][15], applied[15][15], pict[15][15];

   int i, j, k, l, counter;
   cin>>n; 
   
   while(n--)//big loop
   {
      cin>>size;

      for (i=0; i<size; i++)//grid input, substituting y and w for 1 and 0
      {
         for (j=0; j<size; j++)
         {
            cin>>input[i][j];
            if (input[i][j]=='y')
            {
               pict[i][j] = 1;
               savepic[i][j] = 1;
            }
            else
            {
               pict[i][j] = 0;
               savepic[i][j] = 0;
            }
         }
      }
   
      for(i=0; i<pow(2.0, size); i++)
      {
         temp = i;
         memcpy(pict, savepic, sizeof(savepic));
         memset(applied, 0, sizeof(applied));
         
         for(j=0; j<size; j++)
         {
            applied[0][j] = temp%2;
            temp = temp/2;
         }
         for(j=0; j<size; j++)
         {
            for(k=0; k<size; k++)
            {
               if(applied[j][k])
                  paint(pict, j, k);
            }
            for(k=0;k<size; k++)
            {
               if(pict[j][k])
                  applied[j][k] = 1;
            }
         }
         for (l=0; l<size; l++)
            if(pict[size][l]) break;

         if (l==size)
         {
            for(j=0;j<size;j++)
            {
               for(k=0;k<size;k++)
               {
                  if(applied[j][k]!=0)
                     counter++;
               }
            }
            cout<<counter<<endl;
            break;
         }
      }
      if(i==pow(2.0, size))
         cout<<"inf"<<endl;
   }
   return 0;
}

[PAV]

Проверьте последнюю строчку в функции paint

Добавлено спустя 1 минуту 19 секунд:

Где при использовании функции paint проверяется невыход за границы массивов (при окрашивании крайних кирпичей или верхней и нижней строки)?