7.Knight Game / C# Advanced
Нещо не мога да разбера условието на задачата моля за помощ и разяснение, като допълнение може и готови решения!
Условие:
7.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
|
Input |
Output |
|
5 0K0K0 K000K 00K00 K000K 0K0K0 |
1
|
|
2 KK KK |
0 |
|
8 0K0KKK00 0K00KKKK 00K0000K KKKKKK0K K0K0000K KK00000K 00K0K000 000K00KK |
12 |
Здравейте,
може ли някой да сподели решението, което е с рекурсия? Във Фундаментал модула само се е споменавало за нея, но не сме решавали задачи. На интервюта знам, че питат за нея много често.
Разиграх с дадените инпути на реална шахматна дъска- махам един по един конете, които атакуват най-голям брой други коне, докато не остане нито един кон, който да атакува. Мога да кажа, че броя на реално извадените фигури съвпадаше с броя на изтритите в програмата. Може би неточности ще се получават, ако е с по-голям брой числа.
Ето давам и фигурите на дъската, които остават при въвеждането на последния инпут с брой редици 8, при който резултата си е 12, поне доколкото мога да видя. Накрая ми остават точно 12 извадени фигури и тези фигури на дъската със следните кординати:
0 К 0 К К К 0 0
0 0 0 0 К 0 0 0
0 0 0 0 0 0 0 К
К К 0 0 К 0 0 К
К 0 0 0 0 0 0 К
0 0 0 0 0 0 0 К
0 0 К 0 К 0 0 0
0 0 0 К 0 0 0 К
Информативно показвам и начина, който демонстрират в СофтУни за решението на задачата- https://pastebin.com/yxKifU77 , за която все още не успявам да осъзная защо не е съвсем коректна. Ако някой може нека да даде реални инпути, които да разиграя на шахматната дъска за да видя и усмисля правилното решение на задачата.
Предварително благодаря!
@Elena123456
Колегата anton_fotev е дал примерен инпут, при който приложеното решение не работи коректно:
Програмата ще изведе като резултат 4, вместо 3.
Това е, защото кодът използва greedy алгоритъм, който не е удачен в случая (не успява да открие най-оптималното решение).
Благодаря за повторното разяснение. Като споменахте и за greedy алгоритъма и след като отново видях примера, разбрах какво се има предвид. Спомням си, че този алгоритъм го имаше и при RegEx, но можехме да направим така, че изрично да кажем на програмата, че искаме да изключи greedy алгоритъма. Мисля, че това ставаше, като пишехме "?" накрая. Не можем ли и в този случай по някакъв начин да постигнем това- да изключим greedy алгоритъма?
@Elena123456
В RegEx има Greedy and lazy quantifiers.
За тази задача трябва да се напише решение, което анализира всички възможни варианти и избира този, при който се премахват най-малко фигури за да бъде изпълнено условието. Обикновенно подобни решения са по-сложни за писане често са по-тежки за обработка от компютрите в сравнение с greedy подхода, който - ако е правилно написан, ще намери решение, но може и да не е най-оптималното такова. Друга особеност на greedy решението е, че може да върне различен резултат, ако променим посоката на обхождане на дъската или на фигурите.
Имаш ли решение на, С#?