Soluție HackerRank pentru Queen’s Attack II. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Queen’s Attack II

Cerinta completa

You will be given a square chess board with one queen and a number of obstacles placed on it. Determine how many squares the queen can attack.

A queen is standing on an [Expresie matematică indisponibilă în copia arhivată] chessboard. The chess board’s rows are numbered from [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată], going from bottom to top. Its columns are numbered from [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată], going from left to right. Each square is referenced by a tuple, [Expresie matematică indisponibilă în copia arhivată], describing the row, [Expresie matematică indisponibilă în copia arhivată], and column, [Expresie matematică indisponibilă în copia arhivată], where the square is located.

The queen is standing at position [Expresie matematică indisponibilă în copia arhivată]. In a single move, she can attack any square in any of the eight directions (left, right, up, down, and the four diagonals). In the diagram below, the green circles denote all the cells the queen can attack from [Expresie matematică indisponibilă în copia arhivată]:

image

There are obstacles on the chessboard, each preventing the queen from attacking any square beyond it on that path. For example, an obstacle at location [Expresie matematică indisponibilă în copia arhivată] in the diagram above prevents the queen from attacking cells [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată]:

image

Given the queen’s position and the locations of all the obstacles, find and print the number of squares the queen can attack from her position at [Expresie matematică indisponibilă în copia arhivată]. In the board above, there are [Expresie matematică indisponibilă în copia arhivată] such squares.

Function Description

Complete the queensAttack function in the editor below.

queensAttack has the following parameters:
– int n: the number of rows and columns in the board
– nt k: the number of obstacles on the board
– int r_q: the row number of the queen’s position
– int c_q: the column number of the queen’s position
– int obstacles[k][2]: each element is an array of [Expresie matematică indisponibilă în copia arhivată] integers, the row and column of an obstacle

Returns
– int: the number of squares the queen can attack

Input Format

The first line contains two space-separated integers [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], the length of the board’s sides and the number of obstacles.
The next line contains two space-separated integers [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], the queen’s row and column position.
Each of the next [Expresie matematică indisponibilă în copia arhivată] lines contains two space-separated integers [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], the row and column position of [Expresie matematică indisponibilă în copia arhivată].

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • A single cell may contain more than one obstacle.
  • There will never be an obstacle at the position where the queen is located.

Subtasks

For [Expresie matematică indisponibilă în copia arhivată] of the maximum score:

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]

For [Expresie matematică indisponibilă în copia arhivată] of the maximum score:

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]

Sample Input 0

4 0
4 4

Sample Output 0

9

Explanation 0

The queen is standing at position [Expresie matematică indisponibilă în copia arhivată] on a [Expresie matematică indisponibilă în copia arhivată] chessboard with no obstacles:

image

Sample Input 1

5 3
4 3
5 5
4 2
2 3

Sample Output 1

10

Explanation 1

The queen is standing at position [Expresie matematică indisponibilă în copia arhivată] on a [Expresie matematică indisponibilă în copia arhivată] chessboard with [Expresie matematică indisponibilă în copia arhivată] obstacles:

image

The number of squares she can attack from that position is [Expresie matematică indisponibilă în copia arhivată].

Sample Input 2

1 0
1 1

Sample Output 2

0

Explanation 2

Since there is only one square, and the queen is on it, the queen can move 0 squares.

Limbajul de programare folosit: python3

Cod:

#!/bin/python3

def queensAttack(n, k, r_q, c_q, obstacles):
    d = {
        (-1, 0): r_q - 1,
        (1, 0): n - r_q,
        (0, -1): c_q - 1,
        (0, 1): n - c_q,
        (-1, -1): min(r_q - 1, c_q - 1),
        (-1, 1): min(r_q - 1, n - c_q),
        (1, -1): min(n - r_q, c_q - 1),
        (1, 1): min(n - r_q, n - c_q),
    }

    for r, c in obstacles:
        dr = r - r_q
        dc = c - c_q
        sdr = 0 if dr == 0 else (1 if dr > 0 else -1)
        sdc = 0 if dc == 0 else (1 if dc > 0 else -1)

        if dr == 0 or dc == 0 or abs(dr) == abs(dc):
            step = max(abs(dr), abs(dc)) - 1
            key = (sdr, sdc)
            if key in d and step < d[key]:
                d[key] = step

    return sum(d.values())

if __name__ == '__main__':
    n, k = map(int, input().split())
    r_q, c_q = map(int, input().split())
    obstacles = [tuple(map(int, input().split())) for _ in range(k)]
    print(queensAttack(n, k, r_q, c_q, obstacles))

Scor obtinut: 1.0

Submission ID: 464588468

Link challenge: https://www.hackerrank.com/challenges/queens-attack-2/problem

Queen’s Attack II