Loading...
luskos avatar luskos 5 Точки

Multidimensional Arrays Exercise - Knights Game - 10 точки

Настоящото решение минава нулевите тестове с финес, но дава само 10 точки.

https://pastebin.com/QycJmggC

Има закоментирана част която съм използвал само за да си визуализирам таблото.

За всеки Рицар се проверява колко други може да порази, т.е. всички възможни L хода на които е способен във всички посоки.

Има идентична матрица danger, която обаче си служи с цели числа и за всеки рицар използва неговият dangerLevel.

В while цикъл от count (макс. възможен dangerLevel = 8) до 1 се завъртат Рицарите и се премахват един по един за всеки зададен dangerLevel. В случай че dangerLevel = 1 това означава че са останали само рицари които имат по един ход, т.е. достатъчно е да се премахнат само половината, за да е вярно условието за най-малък премахнат брой. Вместо това се премахват всичките и в променливата removedLowestDanger се добавя техният брой след, което от removedKnights се премахва removedLowestDanger / 2 (половината).

Работи със зададените тестове и ги минава.

 

Тагове:
0
C# Advanced
TeodorStefanovPld avatar TeodorStefanovPld 1274 Точки

ами ти яко си hardcod-нал нещата. тоя count 8 идея си нямам защо си го взел и сравняваш по него.

А и от теб се иска да махнеш този с най-много Hits ако правилно помня задачата и после на следващия цикъл другия и така докато не останат.

0
krum_43 avatar krum_43 756 Точки

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

 

0
luskos avatar luskos 5 Точки
  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 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
luskos avatar luskos 5 Точки

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, защото останалите рицари нямат валиден ход, понеже единственият ход на останалите е да ударят този в средата.

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

0
TeodorStefanovPld avatar TeodorStefanovPld 1274 Точки

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

0
luskos avatar luskos 5 Точки

Да кажем че ми дадеш таблица 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--;

0
05/10/2019 11:06:18
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.