Олимпиадная задача по программированию

[c68c15]

Доброго времени суток. Помогите решить задачу по программированию (С++). Что то не какие идеи не приходят в голову... Тут наверное нужно использовать какой то умный очень алгоритм, что то типа жадного... в общим я не знаю.
Вот сам задача:

Имеем таблицу размером N * M , в каждой ячейке которой записана цифра 0 или 1 . На каждом шаге вы можете выбрать одну ячейку и поменять значения во всех ячейках , которые находятся в той же строке или в том же столбце , на противоположные. Таким образом , на каждом шагу Вы меняете ровно N + M -1 ячеек .
Определить минимальное количество шагов необходимых для того , чтобы превратить все ячейки данной таблицы в 0 . Количество строк и столбцов - четные числа . Например , если вы выбрали ячейку ( 2,2 ) :
1 1 1
1 0 1
0 1 1
та следующая будет иметь вид->
1 0 0
0 0 1
0 1 1
Входные данные
Первая строка содержит два целых числа M и N ( 2 < N , M < 1000). Далее N строк по M целых чисел - описание таблицы ( каждое число 0 так 1). N и M - парные .
выходные данные
Одно число - минимальное количество шагов , которые необходимы , чтобы превратить все ячейки таблицы в 0 .

Например, дано таблицу:
Пример 1
2 2
1 0
1 0
Ответ будет: 2

Пример 2
4 4
0 0 1 0
0 1 0 1
1 1 1 0
0 0 1 0
ответ будет: 9

Спасибо заранее за помощь!