Форум программистов, компьютерный форум CyberForum.ru

Задача - C++

Восстановить пароль Регистрация
 
Tarik20
 Аватар для Tarik20
21 / 22 / 2
Регистрация: 14.02.2013
Сообщений: 242
05.11.2013, 21:11     Задача #1
Доброго времени суток. Помогите решить задачу по программированию (С++). Что то не какие идеи не приходят в голову... Тут наверное нужно использовать какой то умный очень алгоритм, что то типа жадного... в общим я не знаю.
Вот сам задача:
Имеем таблицу размером 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
Спасибо заранее за помощь!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 02:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru