Олимпиадные задачи

Перестановки матриц

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

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

Например, если поменять местами первый и третий столбец и первую и третью строку у матрицы

$$\begin{bmatrix} 1 & 2 &3 &4\\ 5 &6 &7 &8\\ 9 &10 &11& 12\\ 13 &14 &15& 16\\ \end{bmatrix}$$

то получим такую матрицу:

$$\begin{bmatrix} 11 & 10 &9 &12\\ 7 &6 &5 &8\\ 3 &2 & 1 & 4\\ 15 &14 &13& 16\\ \end{bmatrix}$$

Требуется найти алгоритм быстрее $O(n!)$.