А какво е условието на задачата ?

1. Knight Game

Chess is the oldest game, but it is still popular these days. For this task we will use only one chess piece – the Knight.

The knight moves to the nearest square but not on the same row, column, or diagonal. (This can be thought of as moving two squares horizontally, then one square vertically, or moving one square horizontally then two squares vertically— i.e. in an "L" pattern.) 

The knight game is played on a board with dimensions N x N and a lot of chess knights 0 <= K <= N2.

You will receive a board with K for knights and '0' for empty cells. Your task is to remove a minimum of the knights, so there will be no knights left that can attack another knight.

Input

On the first line, you will receive the N size of the board

On the next N lines, you will receive strings with Ks and 0s.

Output

Print a single integer with the minimum number of knights that needs to be removed

Constraints

• Size of the board will be 0 < N < 30

• Time limit: 0.3 sec. Memory limit: 16 MB.

Examples

8 е най-големият брой възможни поразяващи ходове които един Рицар може да направи, от там съм го взел. 

0K0K0

K000K

00K00

K000K

0K0K0

Този пример отразява точно това, рицарят в средата има точно 8 възможни хода. Започва се от 8 надолу. Рицарите с 8 хода се премахват и се отбелязва колко са, после тези със 7 ако има, 6,5,4,3,2... и като останат рицари с 1 възможен ход, то е нужно да се премахнат само половината и да се добавят към минималният брой удовлетворяващ условието. Можеш да махнеш коментарите които съм сложил и ще ти се принтира идентична на дъската матрица, като на мястото на рицарите стои броят възможни ходове които могат да направят. Пусни го да ти го изпринтира и може да ти стане ясно как работи. По-горе също съм го обяснил. В конкретният случай като махнеш рицарият с 8 хода е достатъчно, никой друг не може да отбележи върху друг, и в допълнителната матрица всички се зануляват понеже не могат да ударят друг рицар. Няма как да не го хардкоднеш това, просто винаги максималният брой възможни ходове е 8, така стоят нещата просто.

В първа итерация (count = 8) би изглеждало така:

01010

10001

00800

10001

01010

След като се махне рицарят с 8 хода. Всички полета стават 0, защото останалите рицари нямат валиден ход, понеже единственият ход на останалите е да ударят този в средата.

Поне до колкото ми се струва това би трябвало да работи. И на тестовете наистина работи.

да де ама ако ти дам по малка таблица в която коня може да удари 2 полета :Д защо реши че винаги ще може да удря  по 8 ? :Д

Да кажем че ми дадеш таблица 3x3 и кон на x:0 y:0 може да направи само 2 хода, в такъв случай няма да се намери кон който да може да направи нито 8, нито повече от 2, това обаче не пречи на изпълнението на кода по никакъв начин. Просто няма да намери такъв кон и ще продължи да сваля надолу до 2, когато стигне до там ще се изпълни по същият начин както в таблица 30x30. Въртят се няколко наглед празни итерации в този случай, но не съм си поставял за цел да го оптимизирам понеже не гърми за време така или иначе. Започва се от максималният потенциал на рицарите и се сваля надолу защото премахвайки ги по този начин наистина би трябвало да махне минимален брой фигури от дъската.

Вникни в идеята и/или разгледай кода. Не вярвам че judge гърми понеже съм сложил твърда 8-ца, иначе ако е така смятам че е започнал да се самоосъзнава.

Вярвам че нито си разгледал кода нито си го тествал, нито си го дебъгвал @TeodorStefanovPld на тебе ти е смешно, а аз се чувствам като някакъв овчар... Потенциала на един рицар е винаги 8, за това се почва от 8! Това че от големината на дъската или позицията му върху нея, както и позицията на останалите рицари зависи дали потенциалът му е пълен не променя нещата. Програмата си ги търси от 8 до 1 и ако ги намери ги маха ако не ги намери, здраве да е count -= 1 и следващият да заповяда...Може и да има рицар с 8 хода може и да няма, може и да има рицар с 5 хода, но пак може и да няма. Където има ги маха, където няма - не ги маха! Махайки от най-висок потенциал 8, към най-нисък се променят потенциалните ходове на останалите също, а това че не е намерило рицари с определен потенциал не пречи, това е brute force метод за намиране, обхождане на цялата матрица за всеки потенциал от край до край.

Ето примерче по ваш вкус, малка матрица с по-малко от 8 възможни хода и на ум ги смятам че трябва да се махнат 2 рицаря, програмата изплюва резултат 2, следователно аргументите за твърдата 8-ца са невалидни.

3
K00
00K
KK0

200
002
110

EDIT:

На мястото на count-- сложих следният код:

                bool resumeSearch = false;
                foreach (int cell in danger)
                {
                    if (cell == count)
                    {
                        resumeSearch = true;
                        break;
                    }
                }

                if (resumeSearch == false)
                {
                    count--;
                }

Което го оправи. След всеки намерен рицар и премахнат се започва ново търсене извън тялото на двата вложени цикъла които се грижат за премахването, иначе така премахнат един рицар вече променя потенциала на всички останали и е безпредметно да се маха друг със същият потенциал като се има предвид, че той вече може да има друг такъв, ако двата са си взаимодействали един на друг. И чак след като не са намерени такива с търсеният потенциал count--;