Перевертання корів#10546
Іноді Фермеру Джону доводиться мати справу зі скучаючими підлітками, які вночі приходять на його ферму і перевертають його корів. Одного разу вранці він прокидається і виявляє, що це знову сталося: його n^2 корів почали ніч, пасучись у вигляді ідеальної квадратної сітки n \times n, але тепер деякі з них лежать на боку.
На щастя, Фермер Джон використав деталі від свого трактора та навантажувача, щоб зібрати чудову машину під назвою Cow-Untipperator 3000, яка може одночасно перевертати великі групи корів, допомагаючи йому якнайшвидше поставити всіх корів на ноги. Він може застосувати машину до будь-якого «прямокутника з лівим верхнім кутом» у своїй сітці корів — прямокутної підматриці, що містить корову в лівому верхньому куті всієї сітки. При цьому машина перевертає кожну корову в цьому прямокутнику: корови, що лежать на боку, знову встають на ноги, але, на жаль, корови, які вже стояли, також падають! Іншими словами, машина змінює стан кожної корови в прямокутнику на протилежний.
Фермер Джон вважає, що, застосовуючи машину достатню кількість разів до відповідного набору прямокутників, він зрештою зможе поставити всіх корів на ноги. Допоможіть йому визначити мінімальну кількість застосувань машини, необхідну для цього.
Зауважимо, що застосовувати машину до одного й того ж прямокутника двічі безглуздо, оскільки в результаті стан корів у цьому прямокутнику не зміниться. Тому кожен прямокутник з лівим верхнім кутом слід розглядати для застосування не більше одного разу.
У першому рядку міститься ціле число n~(1 \le n \le 10). У кожному з наступних рядків міститься рядок з символів, кожен з яких дорівнює (корова стоїть на ногах) або (корова лежить на боку).
Виведіть мінімальну кількість застосувань машини Cow-Untipperator 3000, необхідну Фермеру Джону, щоб поставити всіх корів на ноги.
У цьому прикладі, якщо Фермер Джон застосує машину до всієї сітки корів (що є допустимим прямокутником з лівим верхнім кутом), стани корів зміняться наступним чином:
110
000
000Після цього залишиться застосувати машину до прямокутника з лівим верхнім кутом, що містить дві одиниці, і задача буде вирішена. Загалом потрібно всього застосування.
Приклад 1