Максимальное совпадение на графике

Question

У меня есть интересная проблема:
Моя программа должна найти максимальное количество 1. Но это не все!. Если программа «увидела» 1, то она должна очистить весь столбец и строку, в которой находится 1.

У меня проблема:
Я не могу найти максимальное количество 1, я не знаю, как это сделать.

Для вас я сделал небольшой пример, надеюсь, он будет вам понятен. Программа должна работать так:

Есть матрица:

1 0 0 0
1 0 1 1
1 1 1 1
1 0 0 1

Программа нашла 1 (позиция [0][0] Я выделил ее черный ) и очистил строку и столбец:

После этого мы находим следующее 1, очищаем строку и столбец и так далее:

В конце программа должна напечатать количество чёрных ячеек .

В моем примере это 4

Как это сделать в C++ коде? Пожалуйста, помогите мне! Спасибо.

Answer 1

Я предпочитаю делать это следующим образом (см. Код ниже): использовать два цикла «for» и внутри второго использовать условное «if», чтобы добавить третий цикл «for» для установки в 0.

for(int i=0;i<m;i++)
    for(int j=0;j<n;j++)
    {
        if(cow[j][i]==1)
        {
            cnt++;
            for(int k=0;k<n;k++)
                cow[k][i]=cow[j][k]=0;
            break;
        }
    }

Answer 2

непонятно, как вы ищете «следующий» 1 в вашей матрице, и если матрица может содержать только 0 и 1. Но если есть четкое определение того, что «следующий», то вы просто кодируете точно так же, как вы описал это выше. Возможный фрагмент кода выглядит следующим образом (не проверено, даже не скомпилировано):

 bool find_next_one(int&x, int&y, matrix const&M)
 {
   // next is in (col,row) order
   for(; x!=M.size(0); ++x)
     for(; y!=M.size(1); ++y)
       if(M(x,y)==1) return 1;
   return 0;
 }
 int count_one(matrix const&M_original)
 {
   matrix M(M_original); // make copy where we can set elements to 0
   int count=0;
   int x=0,y=0;
   while(find_next_one(x,y,M)) {
     ++count;
     for(int i=0; i!=M.size(1); ++i) M(x,i) = 0;
     for(int i=0; i!=M.size(0); ++i) M(i,y) = 0;
   }
   return count;
 }

Answer 3

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

Учитывая (жестко закодированное) определение матрицы, которое выглядит следующим образом:

struct Matrix4x4
{
    int        m[4][4];
};

Чтобы перебрать все элементы, которые вы хотите написать примерно так:

   Matrix4x4 matrix;

   for (size_t row = 0; row < 4; ++row)
   {
       for (size_t col = 0; col < 4; ++col)
       {
           // do something with 'matrix.m[row][col]'
       }
   }

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

Чтобы обработать строку, вы хотите написать что-то вроде этого:

   void FunctionThatOperatesOnARow(Matrix4x4& matrix, size_t row)
   {
       for (size_t col = 0; col < 4; ++col)
       {
           // do something with 'matrix.m[row][col]'
       }
   }

Для обработки столбца вы хотите написать что-то вроде этого:

   void FunctionThatOperatesOnAColumn(Matrix4x4& matrix, size_t col)
   {
       for (size_t row = 0; row < 4; ++row)
       {
           // do something with 'matrix.m[row][col]'
       }
   }

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

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

Answer 4

Заметил, что это похоже на проверку типа сингулярности матрицы, особенно если используются только 1 и 0.

Вы можете проверить определитель матрицы.Ненулевое значение означает, что оно равно количеству строк и столбцов (если матрица всегда квадратная). Если det (0), тогда используйте любой метод, который вы хотите, чтобы привести матрицу к уменьшенной форме, чтобы увидеть, сколько 0-столбцову вас есть - или просто сначала сделайте уменьшение и идите вниз по диагональному счету.

Черт, сортируя столбцы по их добавленной стоимости, поместит их в диагональную форму для вас.Это также очень легко проверяет наличие 0 столбцов.