Професионална програма
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
anton_fotev avatar anton_fotev 9 Точки

за избора на индекси и аз си го мислех. Според мен не може да стане без рекурсии.
обяснявам защо:

0    0    0    0        0    0    0    0

0    0    0    0     0    0    0    0    0

0    0    0    0     0    K    0    0    0

0    0    0    0     0    0    0    0    0 

K    0    0    0     K    0    0    0    K

0    0    K    0     0    0    K    0    0

При използването на индексиЗаОпасност кодът ще махне рицаря на ред  с индекс за ред: 4-ри и индекс за колона: 4. Неговият индексЗаОпасност е 3-ри. Така обаче ще останат три двойки рицари под взаимен удар. Тоест общият брой махнати рицари трябва да 1 + 3 = 4-ри рицаря.

В действителност трябва да се махнат рицарите, които са посочени с черта под линия. Така ще останат трите рицария по краищата и рицарят в средата. Общият брой махнати рицари при втория вариант ще е само три. 
Този втори вариант обаче изисква логика не по събиране на индексиЗаОпасност, а преглеждане на всички възможни пермутации (с изрязване на вариантите, в които рекурсията води до махане на повече коне от досегашен изчислен вариант).



 

3
05/02/2020 22:02:23
Elena123456 avatar Elena123456 224 Точки

Здравейте,

може ли някой да сподели решението, което е с рекурсия? Във Фундаментал модула само се е споменавало за нея, но не сме решавали задачи. На интервюта знам, че питат за нея много често.

Разиграх с дадените инпути на реална шахматна дъска- махам един по един конете, които атакуват най-голям брой други коне, докато не остане нито един кон, който да атакува. Мога да кажа, че броя на реално извадените фигури съвпадаше с броя на изтритите в програмата. Може би неточности ще се получават, ако е с по-голям брой числа.

Ето давам и фигурите на дъската, които остават при въвеждането на последния инпут с брой редици 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 , за която все още не успявам да осъзная защо не е съвсем коректна. Ако някой може нека да даде реални инпути, които да разиграя на шахматната дъска за да видя и усмисля правилното решение на задачата.

Предварително благодаря!

 

0
MartinBG avatar MartinBG 3907 Точки

@Elena123456 

 Колегата anton_fotev е дал примерен инпут, при който приложеното решение не работи коректно:

9
0000K0000
000000000
00000K000
000000000
K000K000K
00K000K00
000000000
000000000
000000000

Програмата ще изведе като резултат 4, вместо 3.

 

Това е, защото кодът използва greedy алгоритъм, който не е удачен в случая (не успява да открие най-оптималното решение).

1
Elena123456 avatar Elena123456 224 Точки

Благодаря за повторното разяснение. Като споменахте и за greedy алгоритъма и след като отново видях примера, разбрах какво се има предвид. Спомням си, че този алгоритъм го имаше и при RegEx, но можехме да направим така, че изрично да кажем на програмата, че искаме да изключи greedy алгоритъма. Мисля, че това ставаше, като пишехме  "?"  накрая. Не можем ли и в този случай по някакъв начин да постигнем това- да изключим greedy алгоритъма?

0
26/12/2020 11:06:34
ElainEuphemia avatar ElainEuphemia -2 Точки

Опитах се да потърся още някои игри, свързани с тази тема.

По темата за безплатните игри, потребителите, които се интересуват от версията за отключване на играта 2021, вижте among us mod apk

-3
05/01/2021 06:26:34
Valentin.Shumankov avatar Valentin.Shumankov 6 Точки

Колега заповядаи моето решение дано ти е полезно да схванеш задачата .

https://pastebin.com/n1Lvc7mp

100/100

0
bojkonil avatar bojkonil 2 Точки

Здравейте,

След доста мъдрене, измъдрих следното:

за всяко К има максимум 8 позиции, които може да "удари", тоест 8 позиици, които трябва да се проверят и резултата да се сравни с останалите, за да се премахне това К с максимален резултат. Това нещо в цикъл до 0 удара решава проблема с минималния брой, тъй като премахваме един вид в Descending order.

А, тъй като около всяко К  се проверява на 2 елемента разстояние, за да си спестя описване на крайни случаи, просто правя матрицата по-голяма с 2 нулеви клетки от всяка страна (2 реда отгоре, 2 реда отдолу, 2 колони отляво, 2 колони отдясно). По този начин 1 метод, който проверява 8те възможни ударни точки, върши работа за всички позиции в зададената матрица, без Out of range exeption.

Ето и кода, за мазохистите:

https://pastebin.com/tU29hxCg

 

0
Martinzca avatar Martinzca 11 Точки

Привет. Предлагам и моето решение, макар на Python, логиката може лесно да се проследи.

1. Намирам "най-силния" кон, тоест този, който достъпва най-много други коне.

2. Отстранявам най-силния кон, като замествам "К" с "0"

3. Проверявам отново за "най-силен" кон или въобще за кон, който достига поне до 1 друг. Ако няма играта свършва.

n = int(input())
matrix = []

for _ in range(n):
    matrix.append(list(input()))


def look_around(k, matrix):
    power = 0
    # Right down:
    if 0 <= (k[1] + 2) < n and 0 <= (k[0] + 1) < n:
        right_d = (k[0] + 1, k[1] + 2)
        if matrix[right_d[0]][right_d[1]] == 'K':
            power += 1
    # Right up:
    if 0 <= (k[1] + 2) < n and 0 <= (k[0] - 1) < n:
        right_u = (k[0] - 1, k[1] + 2)
        if matrix[right_u[0]][right_u[1]] == 'K':
            power += 1
    # Left down:
    if 0 <= (k[1] - 2) < n and 0 <= (k[0] + 1) < n:
        left_d = (k[0] + 1, k[1] - 2)
        if matrix[left_d[0]][left_d[1]] == 'K':
            power += 1
    # Left up:
    if 0 <= (k[1] - 2) < n and 0 <= (k[0] - 1) < n:
        left_u = (k[0] - 1, k[1] - 2)
        if matrix[left_u[0]][left_u[1]] == 'K':
            power += 1
    # Up left:
    if 0 <= (k[0] - 2) < n and 0 <= (k[1] - 1) < n:
        up_l = (k[0] - 2, k[1] - 1)
        if matrix[up_l[0]][up_l[1]] == 'K':
            power += 1
    # Up right:
    if 0 <= (k[0] - 2) < n and 0 <= (k[1] + 1) < n:
        up_r = (k[0] - 2, k[1] + 1)
        if matrix[up_r[0]][up_r[1]] == 'K':
            power += 1
    # Down left:
    if 0 <= (k[0] + 2) < n and 0 <= (k[1] - 1) < n:
        down_l = (k[0] + 2, k[1] - 1)
        if matrix[down_l[0]][down_l[1]] == 'K':
            power += 1
    # Down right:
    if 0 <= (k[0] + 2) < n and 0 <= (k[1] + 1) < n:
        down_r = (k[0] + 2, k[1] + 1)
        if matrix[down_r[0]][down_r[1]] == 'K':
            power += 1

    return power



def get_knights():
    strongest = (0, 0, 0)
    for r in range(n):
        for c in range(n):
            if matrix[r][c] == 'K':
                klock = (r, c)
                power = look_around(klock, matrix)
                if power > 0 and power > strongest[2]:
                    strongest = (r, c, power)

    return strongest


knights = get_knights()
count = 0

while not knights[2] == 0:
    r, c = knights[0], knights[1]
    matrix[r][c] = '0'
    knights = get_knights()
    count += 1

print(count)

 

1