Queen's Attack II

Queen's Attack II

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 n x n chessboard. The chess board’s rows are numbered from 1 to n, going from bottom to top. Its columns are numbered from 1 to n, going from left to right. Each square is referenced by a tuple, (r, c), describing the row, r, and column, c, where the square is located.

The queen is standing at position (rq, cq). 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 (4, 4):

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 (3, 5) in the diagram above prevents the queen from attacking cells (3, 5), (2, 6), and (1, 7):

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 . In the board above, there are such squares.

Function Description

Complete the queensAttack function in the editor below. It should return an integer that describes the number of squares the queen can attack.

queensAttack has the following parameters:

  • n: an integer, the number of rows and columns in the board
  • k: an integer, the number of obstacles on the board
  • r_q: integer, the row number of the queen’s position
  • c_q: integer, the column number of the queen’s position
  • obstacles: a two dimensional array of integers where each element is an array of 2 integers, the row and column of an obstacle

Input Format

The first line contains two space-separated integers n and k, the length of the board’s sides and the number of obstacles.

The next line contains two space-separated integers rq and cq, the queen’s row and column position.

Each of the next k lines contains two space-separated integers r[i] and c[i], the row and column position of obstacle[i].

Constraints

  • 1 <= n <= 105
  • 1 <= k <= 105
  • 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 30% of the maximum score:

  • 0 < n <= 100
  • 0 <= k <= 100

For 55% of the maximum score:

  • 0 < n <= 1000
  • 0 <= k <= 105

Output Format

Print the number of squares that the queen can attack from position (rq, cq)

Sample Input 0

1
2
4 0
4 4

Sample Output 0

1
9

Explanation 0

The queen is standing at position (4, 4) on a 4 x 4 chessboard with no obstacles:

Sample Input 1

1
2
3
4
5
5 3
4 3
5 5
4 2
2 3

Sample Output 1

1
10

Explanation 1

The queen is standing at position (4, 3) on a 5 x 5 chessboard with k = 3 obstacles:

The number of squares she can attack from that position is 10.

Sample Input 2

1
2
1 0
1 1

Sample Output 2

1
0

Explanation 2

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


Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Complete the queensAttack function below.
function queensAttack(n, k, r_q, c_q, obstacles) {
let up = n - r_q;
let right = n - c_q;
let down = r_q - 1;
let left = c_q - 1;

let up_left = Math.min(up, left);
let up_right = n - Math.max(c_q, r_q);
let down_left = Math.min(c_q, r_q) - 1;
let down_right = Math.min(r_q - 1, n - c_q);

for (let i of Array.from({ length: k }, (value, index) => index)) {
let { 0: r_o, 1: c_o } = obstacles[i];

r_o == r_q &&
(c_o > c_q
? (up = Math.min(up, c_o - c_q - 1))
: (down = Math.min(down, c_q - c_o - 1)));

c_o == c_q &&
(r_o > r_q
? (right = Math.min(right, r_o - r_q - 1))
: (left = Math.min(left, r_q - r_o - 1)));

Math.abs(c_o - c_q) == Math.abs(r_o - r_q) &&
(c_o > c_q && r_o > r_q && (up_right = Math.min(up_right, c_o - c_q - 1)),
c_o > c_q &&
r_o < r_q &&
(down_right = Math.min(down_right, c_o - c_q - 1)),
c_o < c_q && r_o > r_q && (up_left = Math.min(up_left, c_q - c_o - 1)),
c_o < c_q &&
r_o < r_q &&
(down_left = Math.min(down_left, c_q - c_o - 1)));
}

return right + left + up + down + down_left + up_left + down_right + up_right;
}
Buy Me A Coffee

Comments

10Days of JS 30Days of Code Algorithm Android Debug Bridge Android Debugging Basic for Web Blog Browsers Chrome으로 Android Debugging 방법 Correctness and the Loop Invariant hackerrank solution in javascript Debug Tools Development Environment in MacOS ES6 Front-End Funny String of Algorithms hackerrank solution in javascript Funny String of Algorithms hackerrank solution in typescript Generator Github Page with Hexo Github Pages HackerRank HackerRank in a String of Algorithms hackerrank solution in javascript HackerRank in a String of Algorithms hackerrank solution in typescript Hexo Hexo Icarus theme Hexo 블로그 만들기 Hexo+Github How Browsers work Insertion Sort - Part 1 hackerrank solution in javascript Insertion Sort - Part 2 hackerrank solution in javascript JS Library JavaScript Level1 Level2 Loops MacOS 개발 환경 설정하기 Mobile web Debugging Node.js Pangrams of Algorithms hackerrank solution in javascript Pangrams of Algorithms hackerrank solution in typescript Problem Solving Programmers Quicksort 1 - Partition hackerrank solution in javascript React RoadMap Running Time of Algorithms hackerrank solution in javascript Safari Debugging Safari Technology Preview Settings Sorting String Strings Strong Password of Algorithms hackerrank solution in javascript TypeScript blog iPhone Safari Debugging 방법 insertion sort 모바일 웹 디버깅 아이폰 사파리를 디버깅하는 방법 안드로이드 디버그 브리지 안드로이드 디버깅하는 방법
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×