  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 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 + 2) < n and 0 <= (k + 1) < n:
right_d = (k + 1, k + 2)
if matrix[right_d][right_d] == 'K':
power += 1
# Right up:
if 0 <= (k + 2) < n and 0 <= (k - 1) < n:
right_u = (k - 1, k + 2)
if matrix[right_u][right_u] == 'K':
power += 1
# Left down:
if 0 <= (k - 2) < n and 0 <= (k + 1) < n:
left_d = (k + 1, k - 2)
if matrix[left_d][left_d] == 'K':
power += 1
# Left up:
if 0 <= (k - 2) < n and 0 <= (k - 1) < n:
left_u = (k - 1, k - 2)
if matrix[left_u][left_u] == 'K':
power += 1
# Up left:
if 0 <= (k - 2) < n and 0 <= (k - 1) < n:
up_l = (k - 2, k - 1)
if matrix[up_l][up_l] == 'K':
power += 1
# Up right:
if 0 <= (k - 2) < n and 0 <= (k + 1) < n:
up_r = (k - 2, k + 1)
if matrix[up_r][up_r] == 'K':
power += 1
# Down left:
if 0 <= (k + 2) < n and 0 <= (k - 1) < n:
down_l = (k + 2, k - 1)
if matrix[down_l][down_l] == 'K':
power += 1
# Down right:
if 0 <= (k + 2) < n and 0 <= (k + 1) < n:
down_r = (k + 2, k + 1)
if matrix[down_r][down_r] == '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:
strongest = (r, c, power)

return strongest

knights = get_knights()
count = 0

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

print(count)
``````

1