Поиск не пересекающихся нулей в матрице

[Armageddets]

Всем доброго времени суток. Столкнулся с проблемой. Есть матрица квадратная, например:

0 4 7 0
5 8 0 4
9 0 5 9
7 3 0 0

Нужно найти столько не пересекающихся нулей, какого размера и сама матрица. Эта матрица размера 4 на 4, поэтому надо найти 4 нуля. Когда в матрице всего 4 нуля то проверить пересекаются они или нет - легко. А вот когда их 6, как здесь то выбрать из них не пересекающиеся сложнее.

[Bugrimov]

А что значит не пересекающиеся нули.

[Аватар]

Язык китайский? И чем отличается "легко" для 4 и "сложно" для 6?

[Arigato]

Так 0 и не имеет пересечений. Вот цифра 4 пересекается или 7, но с палочкой посередине

[Armageddets]

Ну смотрите. Нужно из всех нулей выбрать те, которые не будут находится по координатам икс и игрек с другими выбранными. Например в последнем столбце ноль пересекается с нулем из первого столбца и в этом же столбце тоже есть еще один ноль - поэтому сразу неясно какой из этих нулей брать. В итоге после выбранных нулей должно быть найдено оптимальное решение - выбрать 4 нуля, которые находятся в разных столбцах и в разных строках (ни один из ноликов не должен быть в одной строке или столбце с другим выбранным нулем), например решение такое:

Выбранные нули с координатами (1,1), (2,3), (3,2), (4,4).

Если из матрицы все лишнее удалить то получится:

0 _ _ _
_ _ 0 _
_ 0 _ _
_ _ _ 0

Ни у одного из этих нулей ни повторяется ни одна из координат. Как это реализовать я не знаю. Мне видется вариант примерно такой: сначала находим нолик, в столбце и строке которого больше нет нулей и выбираем его, затем просто находим все нули которые не повторяют координаты ни икс не игрек уже найденных нулей. Но мне кажется такой алгоритм может не всегда срабатывать. Особенно, если не будет нулей в ряду и столбце которых больше не будет нулей.

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

[Armageddets]

Легко для 4, означает, что когда всего есть 4 нуля то проверить их легко. Так как нам ничего больше не остается как брать имеющиеся нули и смотреть не повторяются ли их строки и столбцы?

А вот когда нулей больше, то сложно определить какие же из них выбирать?

[Armageddets]

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

[Аватар]

В каждой строке считать количество нулей и если один - считать количество нулей в соответствующем столбце. Если один - то что нужно. И это без разницы, что для 4, что для 6

[Armageddets]

А если у нас будет такая матрица

4 0 5 0
0 2 0 0
2 4 0 1
0 0 3 5

у нас по два нуля в одной строке и по два в каждом столбце?

[Armageddets]

Можно чтобы в этой строке или столбце были еще нули. Нельзя только чтобы выбранные (те которые мы выберем) находились в одной строке или столбце