# Queen’s Attack II – HackerRank Solution

In this post, we will solve Queen’s Attack II HackerRank Solution. This problem (Queen’s Attack II) is a part of HackerRank Algorithms series.

Contents

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Â (rq, cq). In the board above, there areÂ 24Â 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Â 2Â 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Â 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

• 0 < n <= 105
• 0 < 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.

ForÂ 30%Â of the maximum score:

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

ForÂ 55%Â of the maximum score:

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

Sample Input 0

``````4 0
4 4``````

Sample Output 0

``9``

Explanation 0

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

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Â (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 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.

## Solution – Queen’s Attack II – HackerRank Solution

### C++

```#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef pair < int, int > ii;

int di[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dj[] = {-1, 0, 1, 1, 1, 0, -1, -1};

set < ii > obstacles;
int n, k;
int rQueen;
int cQueen;

void dfs(int r, int c, int dir) {
if (r < 1 || r > n || c < 1 || c > n) return;
if (obstacles.find(ii(r, c)) != obstacles.end()) return;
if (r == rQueen && c == cQueen) answer --;
dfs(r+di[dir], c+dj[dir], dir);
}

int main(){
cin >> n >> k;
cin >> rQueen >> cQueen;
for(int a0 = 0; a0 < k; a0++){
int rObstacle;
int cObstacle;
cin >> rObstacle >> cObstacle;
obstacles.insert(ii(rObstacle, cObstacle));
}

for (int i=0; i<8; i++) {
dfs(rQueen, cQueen, i);
}

cout << answer << endl;

return 0;
}
```

### Python

```#!/bin/python3

import sys
from collections import defaultdict
from math import fabs

def check_diag(queen, obst):
if queen[1] == obst[1]:
return 0
check = (queen[0] - obst[0])/(queen[1] - obst[1])
if fabs(check) == 1.0:
return int(check)
else:
return 0

def queensAttack(n, k, r_q, c_q, obstacles):
queen = [r_q, c_q]
res = 0
obst_by_row = list(filter(lambda x: x[0] == r_q, obstacles))
obst_by_col = list(filter(lambda x: x[1] == c_q, obstacles))
obst_by_plus_diag = list(filter(lambda x: check_diag(queen, x) == 1, obstacles))
obst_by_neg_diag = list(filter(lambda x: check_diag(queen, x) == -1, obstacles))

if not obst_by_col:
res += n-1
else:
obst_higher = list(filter(lambda x: x[0] > r_q, obst_by_col))
if obst_higher:
min_higher = min(obst_higher, key = lambda x: x[0])[0]
else:
min_higher = n+1

obst_lower = list(filter(lambda x: x[0] < r_q, obst_by_col))
if obst_lower:
max_lower = max(obst_lower, key = lambda x: x[0])[0]
else:
max_lower = 0

#print("high = {} low = {}".format(min_higher, max_lower))
res += min_higher - max_lower - 2

if not obst_by_row:
res += n-1
else:
obst_higher = list(filter(lambda x: x[1] > c_q, obst_by_row))
if obst_higher:
min_higher = min(obst_higher, key = lambda x: x[1])[1]
else:
min_higher = n+1

obst_lower = list(filter(lambda x: x[1] < c_q, obst_by_row))
if obst_lower:
max_lower = max(obst_lower, key = lambda x: x[1])[1]
else:
max_lower = 0

#print("high = {} low = {}".format(min_higher, max_lower))
res += min_higher - max_lower - 2

# diagonals
if not obst_by_plus_diag:
res += n-1 - abs(r_q - c_q)
#res += min(n - c_q, n - r_q) + min(c_q - 1, r_q - 1) # = n-1 + min(-c_q, -r_q) + min(c_q, r_q)
#print("res = {}".format(res))
else:
obst_higher = list(filter(lambda x: x[0] > r_q, obst_by_plus_diag))
if obst_higher:
min_higher = min(obst_higher, key = lambda x: x[0])[0]
else:
min_higher = n+1

obst_lower = list(filter(lambda x: x[0] < r_q, obst_by_plus_diag))
if obst_lower:
max_lower = max(obst_lower, key = lambda x: x[0])[0]
else:
max_lower = 0

#print("high = {} low = {}".format(min_higher, max_lower))
res += min_higher - max_lower - 2 - abs(r_q - c_q)

if not obst_by_neg_diag:
#print("n - c_q + r_q = {} - {} + {}".format(n, c_q, r_q))
#res += n-1 - abs(n - c_q + r_q)
#print("res = {}".format(res))
#res += min(n - c_q, r_q - 1) + min(c_q - 1, n - r_q)
# 2 variants:
# res += n - c_q + n - r_q = 2n - c_q - r_q
# res += r_q - 1 + c_q - 1 = r_q + c_q - 2
res += min(n - c_q, r_q - 1)
res += min(c_q - 1, n - r_q)
else:
obst_higher = list(filter(lambda x: x[0] > r_q, obst_by_neg_diag))
if obst_higher:
min_higher = min(obst_higher, key = lambda x: x[0])[1]
else:
min_higher = n+1

obst_lower = list(filter(lambda x: x[0] < r_q, obst_by_neg_diag))
if obst_lower:
max_lower = max(obst_lower, key = lambda x: x[0])[1]
else:
max_lower = 0

print("high = {} low = {}".format(min_higher, max_lower))
print("r_q = {} c_q = {}".format(r_q, c_q))
#res += min_higher - max_lower - 2 - abs(n - c_q + r_q)
if max_lower != 0:
res += max_lower - c_q - 1
if min_higher != n+1:
res += c_q - min_higher - 1

return res

# naive
def queensAttack_naive(n, k, r_q, c_q, obstacles):
obst_by_row = list(filter(lambda x: x[0] == r_q, obstacles))
obst_by_col = list(filter(lambda x: x[1] == c_q, obstacles))
obs_dict = gen_obs_dict(obstacles)

res = 0

if not obst_by_col:
res += n-1
else:
for row_ind in range(r_q+1, n+1):
#if not [row_ind, c_q] in obstacles:
key = str(row_ind) + "-" + str(c_q)
if obs_dict[key] != -1:
res += 1
else:
break
for row_ind in range(r_q-1, 0, -1):
#if not [row_ind, c_q] in obstacles:
key = str(row_ind) + "-" + str(c_q)
if obs_dict[key] != -1:
res += 1
else:
break

if not obst_by_row:
res += n-1
else:
for col_ind in range(c_q+1, n+1):
#if not [r_q, col_ind] in obstacles:
key = str(r_q) + "-" + str(col_ind)
if obs_dict[key] != -1:
res += 1
else:
break
for col_ind in range(c_q-1, 0, -1):
#if not [r_q, col_ind] in obstacles:
key = str(r_q) + "-" + str(col_ind)
if obs_dict[key] != -1:
res += 1
else:
break

row_ind, col_ind = r_q+1, c_q+1
while col_ind != 0 and row_ind != 0 and col_ind != n+1 and row_ind != n+1:
#if not [row_ind, col_ind] in obstacles:
key = str(row_ind) + "-" + str(col_ind)
if obs_dict[key] != -1:
res += 1
row_ind += 1
col_ind += 1
else:
break

row_ind, col_ind = r_q-1, c_q+1
while col_ind != 0 and row_ind != 0 and col_ind != n+1 and row_ind != n+1:
#if not [row_ind, col_ind] in obstacles:
key = str(row_ind) + "-" + str(col_ind)
if obs_dict[key] != -1:
res += 1
row_ind -= 1
col_ind += 1
else:
break

row_ind, col_ind = r_q+1, c_q-1
while col_ind != 0 and row_ind != 0 and col_ind != n+1 and row_ind != n+1:
#if not [row_ind, col_ind] in obstacles:
key = str(row_ind) + "-" + str(col_ind)
if obs_dict[key] != -1:
res += 1
row_ind += 1
col_ind -= 1
else:
break

row_ind, col_ind = r_q-1, c_q-1
while col_ind != 0 and row_ind != 0 and col_ind != n+1 and row_ind != n+1:
#if not [row_ind, col_ind] in obstacles:
key = str(row_ind) + "-" + str(col_ind)
if obs_dict[key] != -1:
res += 1
row_ind -= 1
col_ind -= 1
else:
break

return res

def gen_obs_dict(obstacles):
dict_out = defaultdict(int)
for obs in obstacles:
row, col = obs[0], obs[1]
key = str(row) + "-" + str(col)
dict_out[key] = -1

return dict_out

if __name__ == "__main__":
n, k = [int(x) for x in input().strip().split(' ')]
r_q, c_q = [int(x) for x in input().strip().split(' ')]
obstacles = []
for obstacles_i in range(k):
obstacles_t = [int(obstacles_temp) for obstacles_temp in input().strip().split(' ')]
obstacles.append(obstacles_t)
result = queensAttack_naive(n, k, r_q, c_q, obstacles)
print(result)
```

### Java

```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int rQ = in.nextInt();
int cQ = in.nextInt();
List<HashSet<Integer>> ll = new ArrayList<HashSet<Integer>>();
List<HashSet<Integer>> ll2 = new ArrayList<HashSet<Integer>>();
for (int i=0;i<=n;i++){
}
for(int a0 = 0; a0 < k; a0++){
int r = in.nextInt();
int c = in.nextInt();

}

long ans = 0;

for (int i=cQ-1;i>=1;i--){
if (ll.get(rQ).contains(i)){
break;
}
ans++;
}

for (int i=cQ+1;i<=n;i++){
if (ll.get(rQ).contains(i)){

break;
}
ans++;
}

for (int i=rQ-1;i>=1;i--){
if (ll2.get(cQ).contains(i)){

break;
}
ans++;
}

for (int i=rQ+1;i<=n;i++){
if (ll2.get(cQ).contains(i)){

break;
}
ans++;
}

int cc = cQ-1;
for (int i=rQ-1;i>=1;i--){
if (cc==0 || ll.get(i).contains(cc)){
break;
}
cc--;
ans++;
}

cc = cQ-1;
for (int i=rQ+1;i<=n;i++){
if (cc==0 || ll.get(i).contains(cc)){
break;
}
cc--;
ans++;
}

cc = cQ+1;
for (int i=rQ+1;i<=n;i++){
if (cc==n+1 || ll.get(i).contains(cc)){
break;
}
cc++;
ans++;
}

cc = cQ+1;
for (int i=rQ-1;i>=1;i--){
if (cc==n+1 || ll.get(i).contains(cc)){
break;
}
cc++;
ans++;
}

System.out.println(ans);
}
}
```

Note: This problem (Queen’s Attack II) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.