HackerRank Queen’s Attack II Solution

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.

HackerRank Queen’s Attack II Solution
HackerRank Queen’s Attack II Solution

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

Ezoicreport this adTask

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.

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, (rc), describing the row, r, and column, c, where the square is located.

The queen is standing at position (rqcq). 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 (rqcq). 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:

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 (4, 3) on a 5 x 5 chessboard with k = 3 obstacles:

image

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);
    }
}
Ezoicreport this ad

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.

Next: HackerRank Halloween Sale Solution

Sharing Is Caring

Leave a Comment

Ezoicreport this ad