Модуль: Перебор всех подмасок данной маски


Задача

5 /7


Эрик и светодиодная плата

Теория Нажмите, чтобы прочитать/скрыть

Бывает, что необходимо перебрать все битовые последовательности определенной длины. Или другими словами, перебрать все возможные варианты, где для каждого объекта выбирается одно из двух возможных состояний.

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

Общий код с использованием битмасок приведен ниже: 
    int n; // количеств ообъектов (длина битовой последовательности)

    for (int mask = 0; mask < (1 << n); mask++) { // перебираем все числа от 0 до 2^n - 1, где каждое число соответствует битовой маске

        // текущее число mask является битовой маской, где i-ый бит задает состояние i-ого объекта

        for (int i = 0; i < n; i++) { // перебираем n бит, чтобы понять какое состояние у какого объекта

            if ((1 << i) & mask) { // проверяем, что i-ый бит равен единице

                // обрабатываем вариант, что у i-ого объекта состояние '1'
            }
            else { // случай, когда i-ый бит равен нулю

                // обрабатываем вариант, что у i-ого обхекта состояния '0'
            }
        }
    }

Такой код работает за О(2^n * f(n)), где f(n) - это время, за которое вы обрабатываете один конкретный перебираемый вариант.

Задача

В старом дедушкином гараже Эрик нашел светодиодную плату. Однако его удивило то, что при активации диоды были не синхронизированы между собой. То есть некоторые из них горели, а некоторые нет.
Сама же плата оказалось необычной. Она представляет собой прямоугольную сетку с n рядами и m столбцами, где в каждой ячейке находится один диод. Около каждого ряда есть рычаг, который переключает все диоды в этом ряду (горящие диоды потухают и наоборот). Такие же рычаги есть и у каждого столбца (которые задействую диоды в соответствующем столбце).
Эрику стало интересно, возможно ли посредством переключения рычагов привести диоды в одинаковое состояние.

Входные данные:
В первой строке даются два натуральных числа n и m (1 <= n, m <= 7) - количество рядов и столбцов на плате соответственно.
Далее идет n строк по m чисел в каждой - состояния диодов, где 0 означает, что диод не горит, и 1, что горит.

Выходные данные:
Выведите "YES", если можно привести диоды в одно состояние и "NO", если нельзя.

Примеры:
 
Входные данные Выходные данные
2 2
0 1
1 0		 YES
2 2
0 1
0 0		 NO

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

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w642
Python1
Комментарий учителя

Напишите программу

или выберите язык программирования и введите исходный код

Auto

       

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!