Multidimensional Arrays Exercise - Knights Game - 10 точки
Настоящото решение минава нулевите тестове с финес, но дава само 10 точки.
Има закоментирана част която съм използвал само за да си визуализирам таблото.
За всеки Рицар се проверява колко други може да порази, т.е. всички възможни L хода на които е способен във всички посоки.
Има идентична матрица danger, която обаче си служи с цели числа и за всеки рицар използва неговият dangerLevel.
В while цикъл от count (макс. възможен dangerLevel = 8) до 1 се завъртат Рицарите и се премахват един по един за всеки зададен dangerLevel. В случай че dangerLevel = 1 това означава че са останали само рицари които имат по един ход, т.е. достатъчно е да се премахнат само половината, за да е вярно условието за най-малък премахнат брой. Вместо това се премахват всичките и в променливата removedLowestDanger се добавя техният брой след, което от removedKnights се премахва removedLowestDanger / 2 (половината).
Работи със зададените тестове и ги минава.
А какво е условието на задачата ?
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 е най-големият брой възможни поразяващи ходове които един Рицар може да направи, от там съм го взел.
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, защото останалите рицари нямат валиден ход, понеже единственият ход на останалите е да ударят този в средата.
Поне до колкото ми се струва това би трябвало да работи. И на тестовете наистина работи.