Професионална програма
Loading...
dido1092 avatar dido1092 37 Точки

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 rowcolumn, 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

Тагове:
0
C# Advanced
Dianov avatar Dianov 13 Точки

Здравей, колега. Ще опитам да разясня логиката на задачата, като използвам първия примерен вход:

0 K 0 K 0

K 0 0 0 K

0 0 K 0 0

K 0 0 0 K

0 K 0 K 0

Първо за хората, които не играят шах, нека да разясним движението на коня - всеки кон се движи на буква Г. При конкретния input единствения кон (knight), който може да извърши ход във всяка една посока без да излезе от дъската е коня в средата (на червения фон) - това са 8 възможни хода във всички посоки (допълнително описание на посоките в link с решението от GitHub, който ще откриете в края на коментара). Както червения кон може да атакува всеки един от сините, така и всеки от сините може да атакува червения, но в условието се иска да се премахнат възможно най-малко коне от дъската, така че всеки кон да не е в състояние да атакува някой от другите в случай, че смени позицията си. Следователно ако решим да премахнем някой от сините коне всички останли все още могат да атакуват червения кон и е необходимо да вадим още фигури. В такъв случай трябва да започнем да вадим първо от фигурите, които имат най-голям потенциал да атакуват. До тук по условието, а сега нека да видим алгоритъма, който съм използвал, за да реша задачата.

Задачата е решена единствено с матрица, 3 вложени for цикъла и if проверки:
1. За представянето на шахматната дъска с фигурите съм използвал матрица. Създаваме я с размерите от входа и попълваме позициите с подадения вход, както се запълват матрици.

2. Най-външният цикъл е низходящ от (i = 8; i > 0; i--), където i всъщност е максималния брой застрашени коне, които може да атакува всяка една фигура в случай, че на всяка една от новите позиции има друг кон (всички нови позиции са заети от друга фигура), а на всяка следваща итерация има с по една незаета позиция.
3. Останалите два вложени цикъла са за обхождане на всеки един индекс от матрицата - board[row, column].
4. Проверка дали на конкретния индекс има фигура. Ако няма - преминаваме към следващия индекс докато стигнем до позиция, където разполагаме с фигура, която да местим по дъската.

5. Като достигнем до индекс, на който има фигура изчисляваме индекса на всяка една нова позиция от възможните максимум 8 хода. Не всяка фигура може да извърши всички ходове без да излезе от дъската, следователно е необходимо в тази проверка да направим проверка дали новия индекс не е извън рамките на матрицата ако не искаме да изгърми с IndexOutOfRangeException. За всеки един нов индекс, който е в рамките на матрицата проверяваме дали на него има кон, който да бъде атакуван. Използвам променлива от тип int за брояч, който отчита на колко от новите позиции има кон.
6. Преди да премина към следващата позиция от шахматната дъска проверявам дали брояча е равен на i от най-външния цикъл, т.е. коня е в състояние да атакува максималния възможен брой други фигури за конкретната итерация. Ако условието е изпълнено премахвам коня (променям стойността от К на '0'), с което приключва пълния цикъл от проверката. Естествено използвам и втора променлива от тип int, която пази броя на извадените фигури.

В случая с примерния input за всеки от сините коне при първото обхождане на дъската, брояча ще е равен на 1, тъй като при всеки от възможните им ходове в рамките на дъската могат да атакуват единствено червения кон. За червения кон обаче брояча е равен на 8. Следователно при първата итерация на най-външния цикъл ще се махне червения кон в центъра. При второто и всяко следващо обхождане брояча, който следи на колко от новите позиции има друг кон ще бъде равен на 0, което не изпълнява условията от проверките описани на т. 5 и т. 6. Така не се стига до премахване на други коне. След края на трите вложени цикъла просто се изпринтва на конзолата стойността в брояча, която следи извадения брой коне.

Линк към решението със C# (100/100 в Judge) с коментари коя част от кода точно за кое отговаря:
http://github.com/DDianovMD/SoftUni/blob/main/CSharpAdvanced/MultidimensionalArraysExercise/KnightGame/Program.cs

Успех!

 

1
08/03/2022 01:49:44
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.