Hello Programmers, In this post, you will know how to solve the HackerRank Queen’s Attack II Solution. This problem is a part of the HackerRank Algorithms Series.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.
HackerRank Queen’s Attack II Solution
Task
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
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
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.
HackerRank Queen’s Attack II solution
Queen’s Attack II 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 II Solution in Cpp
#include <bits/stdc++.h> using namespace std; #define inf 1023456789 #define linf 1023456789123456789ll #define pii pair<int,int> #define pipii pair<int, pii > #define pll pair<long long,long long> #define vint vector<int> #define vvint vector<vint > #define ll long long #define pdd pair<double, double> #define DEBUG #ifdef DEBUG #define db(x) cerr << #x << " = " << x << endl #else #define db(x) #endif int main() { int n, k; scanf("%d %d", &n, &k); int yq, xq; scanf("%d %d", &yq, &xq); int mini[4], maxi[4]; mini[0] = yq-n; maxi[0] = yq-1; mini[1] = max(yq-n, 1-xq); maxi[1] = min(yq-1, n-xq); mini[2] = 1-xq; maxi[2] = n-xq; mini[3] = max(1-yq, 1-xq); maxi[3] = min(n-yq, n-xq); int dX[4] = {0, 1, 1, 1}, dY[4] = {-1, -1, 0, 1}; for(int i=0; i<k; i++) { int y, x; scanf("%d %d", &y, &x); x -= xq; y -= yq; for(int smer=0; smer<4; smer++) { if(y*dX[smer] - x*dY[smer] == 0) { int dist = (y*dY[smer] + x*dX[smer]) / (dY[smer]*dY[smer] + dX[smer]*dX[smer]); if(dist < 0) { mini[smer] = max(mini[smer], dist+1); } else { maxi[smer] = min(maxi[smer], dist-1); } } } } int sum = 0; for(int i=0; i<4; i++)sum += maxi[i] - mini[i]; printf("%d\n", sum); return 0; }
Queen’s Attack II 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 II 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 II Solution using JavaScript
process.stdin.resume(); process.stdin.setEncoding('ascii'); var input_stdin = ""; var input_stdin_array = ""; var input_currentline = 0; process.stdin.on('data', function (data) { input_stdin += data; }); process.stdin.on('end', function () { input_stdin_array = input_stdin.split("\n"); main(); }); function readLine() { return input_stdin_array[input_currentline++]; } /////////////// ignore above this line //////////////////// function main() { var n_temp = readLine().split(' '); var n = parseInt(n_temp[0]); var k = parseInt(n_temp[1]); var rQueen_temp = readLine().split(' '); var rQueen = parseInt(rQueen_temp[0]); var cQueen = parseInt(rQueen_temp[1]); var obstacles = {}; for(var a0 = 0; a0 < k; a0++){ var rObstacle_temp = readLine().split(' '); var rObstacle = parseInt(rObstacle_temp[0]); var cObstacle = parseInt(rObstacle_temp[1]); obstacles[rObstacle + "-" + cObstacle] = true; } var count = 0; var r, c; //search left r = rQueen; for (c = cQueen-1; c > 0; c--) { if (obstacles.hasOwnProperty(r + "-" + c) == true) break; else count++; } //search right for (c = cQueen+1; c <= n; c++) { if (obstacles.hasOwnProperty(r + "-" + c) == true) break; else count++; } //search up c = cQueen; for (r = rQueen+1; r <= n; r++) { if (obstacles.hasOwnProperty(r + "-" + c) == true) break; else count++; } //search down for (r = rQueen-1; r > 0; r--) { if (obstacles.hasOwnProperty(r + "-" + c) == true) break; else count++; } //search up-left for (r = rQueen+1, c = cQueen-1; (r <= n && c > 0); r++, c--) { if (obstacles.hasOwnProperty(r + "-" + c) == true) break; else count++; } //search up-right for (r = rQueen+1, c = cQueen+1; (r <= n && c <= n); r++, c++) { if (obstacles.hasOwnProperty(r + "-" + c) == true) break; else count++; } //search down-left for (r = rQueen-1, c = cQueen-1; (r > 0 && c > 0); r--, c--) { if (obstacles.hasOwnProperty(r + "-" + c) == true) break; else count++; } //search down-right for (r = rQueen-1, c = cQueen+1; (r > 0 && c <= n); r--, c++) { if (obstacles.hasOwnProperty(r + "-" + c) == true) break; else count++; } console.log(count); }
Queen’s Attack II Solution in Scala
object Solution { import scala.collection.mutable.BitSet def main(args: Array[String]) { val sc = new java.util.Scanner (System.in); var n = sc.nextInt(); //n = 100000 var k = sc.nextInt(); var rQueen = sc.nextInt(); var cQueen = sc.nextInt(); var a0 = 0; val rowMultiplier : Long = 100001L var rowSet : Set[Long] = Set[Long](); var colSet : BitSet = BitSet(); def is_obstacle(row: Int,col:Int) : Boolean = { val rowcol : Long = row * rowMultiplier + col rowSet.contains(rowcol) } def move_bishop( row: Int, col: Int): Int = { var nextRow = 0; var nextCol = 0; var num_moves = 0; nextCol = col + 1 nextRow = row + 1 while(nextCol <= n && nextRow <= n && is_obstacle(nextRow,nextCol) == false){ num_moves += 1 nextCol += 1 nextRow += 1 } // down nextCol = col - 1 nextRow = row - 1 while(nextCol > 0 && nextRow > 0 && is_obstacle(nextRow,nextCol) == false) { num_moves += 1 nextCol -= 1 nextRow -= 1 } // right nextRow = row + 1 nextCol = col - 1 while(nextRow <= n && nextCol > 0 && is_obstacle(nextRow,nextCol) == false) { num_moves += 1 nextRow += 1 nextCol -= 1 } // left nextRow = row - 1 nextCol = col + 1 while(nextRow > 0 && nextCol <= n && is_obstacle(nextRow,nextCol) == false) { num_moves += 1 nextRow -= 1 nextCol += 1 } return(num_moves) } def move_root(row: Int, col: Int) : Int = { var nextRow = 0; var nextCol = 0; var num_moves = 0; nextCol = col + 1 while(nextCol <= n && is_obstacle(row,nextCol) == false) { num_moves += 1 nextCol += 1 } // down nextCol = col - 1 while(nextCol > 0 && is_obstacle(row,nextCol) == false) { num_moves += 1 nextCol -= 1 } // right nextRow = row + 1 while(nextRow <= n && is_obstacle(nextRow,col) == false) { num_moves += 1 nextRow += 1 } // left nextRow = row - 1 while(nextRow > 0 && is_obstacle(nextRow,col) == false) { num_moves += 1 nextRow -= 1 } return num_moves; } def move_queen(row: Int, col: Int) : Int = { var nextRow = 0; var nextCol = 0; return move_bishop(row, col) + move_root(row,col); } while(a0 < k){ var rObstacle = sc.nextInt(); var cObstacle = sc.nextInt(); var rowcol: Long = rObstacle * rowMultiplier + cObstacle rowSet = rowSet + rowcol; //colSet = colSet + cObstacle; // your code goes here //println(rObstacle) //println(cObstacle) a0+=1; } var counts = 0; counts = move_queen(rQueen,cQueen) // check and count the moves // check down println(counts) } }
Queen’s Attack II Solution in Pascal
{$mode objfpc} program C; uses fgl; type TIntList = specialize TFPGMap<Integer, Integer>; var Rows: array[0..100000] of TIntList; n: Integer; qr, qc: Integer; function Compare(const i, j: Integer): Integer; begin Result := i - j; end; procedure ReadData; var i, k: Integer; r, c: Integer; begin ReadLn(n, k); ReadLn(qr, qc); for r := 0 to n do begin Rows[r] := TIntList.Create; Rows[r].Sorted := True; end; for i := 1 to k do begin ReadLn(r, c); Rows[r].Add(c, c); end; end; const dc: array [1..8] of Integer = (-1, -1, -1, 0, 0, +1, +1, + 1); dr: array [1..8] of Integer = (-1, 0, +1, -1, +1, -1, 0, + 1); function Solve: Int64; var i, j: Integer; r, c: Integer; begin Result := 0; for i := 1 to 8 do begin r := qr; c := qc; for j := 1 to n do begin if (r + j * dr[i] <= 0) or (c + j * dc[i] <= 0) then break; if (r + j * dr[i] > n) or (c + j * dc[i] > n) then break; if 0 <= Rows[r + j * dr[i]].IndexOf(c + j * dc[i]) then break; Inc(Result); end; end; end; var i: Integer; xi: Integer; begin ReadData; WriteLn(Solve); end.
Disclaimer: This problem (Queen’s Attack II) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.