C ++ код связан с матрицей, сеткой n * n и т. Д.

Question

Кнопка

Каждая ячейка сетки N x N является либо 0, либо 1. Вам даны две такие сетки N x N, начальная и конечная сетка. Есть кнопка против каждой строки и каждого столбца начальной N x N сетки. Нажатие кнопки строки переключает значения всех ячеек в этой строке, а нажатие кнопки столбца переключает значения всех ячеек в этом столбце.

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

Если начальная и конечная конфигурации совпадают, выведите «0».

Input
Первая строка содержит t, количество тестов (около 10). Затем следуют t тестов.

Каждый контрольный пример имеет следующую форму:

• Первая строка содержит n, размер доски (1 ≤ n ≤ 1000).
• следуют n строк. В i-й строке записано n целых чисел, разделенных пробелом, представляющих i-ю строку начальной сетки. Каждое целое число равно 0 или 1.
• n строк, представляющих конечную сетку, в том же формате, что и выше.

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

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

Введите:

1
3
0 0 0
1 1 0
1 1 0
1 1 0
1 1 1
1 1 1

Выход:

1
0
1
2

Несмотря на то, что он работает абсолютно нормально на моей машине, он не принимает решение на codechef и дает мне неправильный ответ. Кто-нибудь может подсказать мне, что делать, пожалуйста, PLS, PLS, PLS?

Код был написан на C ++ и скомпилирован с использованием компилятора g ++.

Answer 1

В размещенном коде я пересмотрю код после того, как вы вычислите "matrixc". Мне очень трудно следовать за этим, поэтому я перестану смотреть на код и говорить о проблеме. Для тех, у кого нет кода, матрица C = начальная матрица - конечная матрица. Матрицы находятся над двоичным полем.

В подобных задачах посмотрите на симметрии в решении. Есть три симметрии. Во-первых, порядок кнопок не имеет значения. Если вы принимаете правильное решение и переставляете его, вы получаете другое правильное решение. Другая симметрия заключается в том, что нажатие кнопки дважды аналогично тому, как вообще не нажимать ее. Последняя симметрия заключается в том, что если вы берете дополнение действительного решения, вы получаете другое действительное решение. Например, в сетке 3x3, если S = ​​{row1, row3, col1} является решением, то S '= {row2, col2, col3} также является решением.

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

Симметрия является очень важной концепцией в информатике, и она встречается почти везде. Понимание симметрии этой проблемы - это то, что позволяет решить ее, не проверяя каждое возможное решение.

P.S. Вы говорите, что этот код - C ++, но он также совершенно допустим, если вы удаляете #include <iostream> сверху. Компиляция может занять гораздо меньше времени, если вы компилируете его как C.