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 chessboard. The chess board’s rows are numbered from to , going from bottom to top. Its columns are numbered from to , going from left to right. Each square is referenced by a tuple, , describing the row, , and column, , where the square is located.
The queen is standing at position . 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 :
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 in the diagram above prevents the queen from attacking cells , , and :
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 integers, the row and column of an obstacle
Input Format
The first line contains two space-separated integers and , the length of the board’s sides and the number of obstacles.
The next line contains two space-separated integers and , the queen’s row and column position.
Each of the next lines contains two space-separated integers and , the row and column position of .
Output Format
Print the number of squares that the queen can attack from position .
Sample Input 0
4 0 4 4
Sample Output 0
9
Explanation 0
The queen is standing at position on a 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 on a chessboard with obstacles:
The number of squares she can attack from that position is .
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.
Queen’s Attack 2 HackerRank Solution in C
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int min(int a,int b){
if(a>b)
return b;
return a;
}
int main(){
int n;
int k;
scanf("%d %d",&n,&k);
int rq,i;
int cq;
int c[8];
scanf("%d %d",&rq,&cq);
c[0] = n-cq;
c[1] = cq-1;
c[2] = n-rq;
c[3] = rq-1;
c[4] = min(rq,cq)-1;
c[5] = min(n-rq,n-cq);
c[6] = min(n-rq,cq-1);
c[7] = min(rq-1,n-cq);
for(int a0 = 0; a0 < k; a0++){
int ro;
int co;
scanf("%d %d",&ro,&co);
if(ro==rq&&(co-cq)>0){
if(c[0]>(co-cq-1))
c[0] = co-cq-1;
//printf("%d %d\n",a0,0);
}
if(ro==rq&&(co-cq)<0){
if(c[1]>(cq-co-1))
c[1] = cq-co-1;
//// printf("%d %d \n",a0,1);
}
if(co==cq&&(ro-rq)>0){
if(c[2]>(ro-rq-1))
c[2]=(ro-rq-1);
// printf("%d %d\n",a0,2);
}
if(co==cq&&(ro-rq)<0){
if(c[3]>(rq-ro-1))
c[3]=(rq-ro-1);
// printf("%d %d\n",a0,3);
}
if((co-cq)==(ro-rq)&&(ro-rq)<0){
if(c[4]>(rq-ro-1))
c[4]=(rq-ro-1);
// printf("%d %d\n",a0,4);
}
if((co-cq)==(ro-rq)&&(ro-rq)>0){
if(c[5]>(ro-rq-1))
c[5]=(ro-rq-1);
//printf("%d %d\n",a0,5);
}
if((co-cq)==(rq-ro)&&(ro-rq)>0){
if(c[6]>(ro-rq-1))
c[6]=(ro-rq-1);
//printf("%d %d\n",a0,6);
}
if((co-cq)==(rq-ro)&&(ro-rq)<0){
if(c[7]>(rq-ro-1))
c[7]=(rq-ro-1);
// printf("%d %d\n",a0,7);
}
// your code goes here
}
int sum=0;
for(i=0;i<8;i++){
sum = sum + c[i];
//printf("%d ",c[i]);
}
printf("%d",sum);
return 0;
}
Queen’s Attack 2 HackerRank Solution in 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;
long long answer;
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;
answer ++;
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;
}
Queen’s Attack 2 HackerRank Solution in 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++){
ll.add(new HashSet<Integer>());
ll2.add(new HashSet<Integer>());
}
for(int a0 = 0; a0 < k; a0++){
int r = in.nextInt();
int c = in.nextInt();
ll.get(r).add(c);
ll2.get(c).add(r);
}
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);
}
}
Queen’s Attack 2 HackerRank Solution in Python
#!/bin/python
import sys
n,k = raw_input().strip().split(' ')
n,k = [int(n),int(k)]
rQueen,cQueen = raw_input().strip().split(' ')
rQueen,cQueen = [int(rQueen),int(cQueen)]
s = set()
for a0 in xrange(k):
rObstacle,cObstacle = raw_input().strip().split(' ')
rObstacle,cObstacle = [int(rObstacle),int(cObstacle)]
s.add((rObstacle, cObstacle))
mx = [0, 1, 1, 1, 0, -1, -1, -1]
my = [-1, -1, 0, 1, 1, 1, 0, -1]
ans = 0
for i in xrange(8):
cur_y, cur_x = rQueen, cQueen
while 0 < cur_y <= n and 0 < cur_x <= n:
if (cur_y, cur_x) not in s:
ans += 1
else:
break
cur_y += my[i]
cur_x += mx[i]
ans -= 1
print ans
Queen’s Attack 2 HackerRank Solution in C#
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution {
static int n;
static void Main(String[] args) {
var tmp = Console.ReadLine().Split(' ');
n = int.Parse(tmp[0]);
int k = int.Parse(tmp[1]);
tmp = Console.ReadLine().Split(' ');
int rq = int.Parse(tmp[0]) - 1;
int cq = int.Parse(tmp[1]) - 1;
HashSet<long> h = new HashSet<long>();
for (int i = 0; i < k; i++) {
tmp = Console.ReadLine().Split(' ');
long a = long.Parse(tmp[0]) - 1;
long b = long.Parse(tmp[1]) - 1;
h.Add(a << 31 | b);
}
long x = 0, y = 0;
int[] _u = { 1, 1, 1, 0, 0, -1, -1, -1 };
int[] _v = { 0, 1, -1, 1, -1, -1, 0, 1 };
int ans = 0;
for (int i = 0; i < 8; i++) {
int u = _u[i], v = _v[i];
x = rq + u; y = cq + v;
while (valid(x, y)) {
if (h.Contains(x << 31 | y)) break;
ans++;
x += u; y += v;
}
}
Console.WriteLine(ans);
}
private static bool valid(long x, long y) {
return x >= 0 && y >= 0 && x < n && y < n;
}
}
Attempt Queen’s Attack 2 HackerRank Challenge
Link – https://www.hackerrank.com/challenges/queens-attack-2/
Next HackerRank Challenge Solution
Link – https://exploringbits.com/acm-icpc-team-hackerrank-solution/
Aayush Kumar Gupta is the founder and creator of ExploringBits, a website dedicated to providing useful content for people passionate about Engineering and Technology. Aayush has completed his Bachelor of Technology (Computer Science & Engineering) from 2018-2022. From July 2022, Aayush has been working as a full-time Devops Engineer.
