HackerRank Queen's Attack II Problem Solution

In this post, we will solve HackerRank Queen’s Attack II Problem Solution.

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 (r, c). 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 (r, c). 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 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 r, and c, 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].

Sample Input 0

4 0
4 4

Sample Output 0

Explanation 0

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

Sample Input 1

Sample Output 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.

Table of Contents

Queen’s Attack II C Solution

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int n; 
    int k; 
    scanf("%d %d",&n,&k);
    int rQueen; 
    int cQueen; 
    scanf("%d %d",&rQueen,&cQueen);
    int pos[8];
    pos[0] = cQueen - 1;
    pos[2] = n - rQueen;
    pos[4] = n - cQueen;
    pos[6] = rQueen - 1;
    pos[1] = cQueen - 1 < n - rQueen ? cQueen - 1 : n - rQueen;
    pos[3] = n - cQueen < n - rQueen ? n - cQueen : n - rQueen;
    pos[5] = n - cQueen < rQueen - 1 ? n - cQueen : rQueen - 1;
    pos[7] = cQueen - 1 < rQueen - 1 ? cQueen - 1 : rQueen - 1;
    for(int a0 = 0; a0 < k; a0++){
        int rObstacle; 
        int cObstacle; 
        scanf("%d %d",&rObstacle,&cObstacle);
        // your code goes here
        int pos_i;
        int r_diff = rObstacle - rQueen;
        int c_diff = cObstacle - cQueen;
        if(r_diff == 0){
            pos_i = c_diff < 0 ? 0 : 4;
            pos[pos_i] = abs(c_diff) - 1 < pos[pos_i] ? abs(c_diff) - 1 : pos[pos_i];
        }
        if(c_diff == 0){
            pos_i = r_diff > 0 ? 2 : 6;
            pos[pos_i] = abs(r_diff) - 1 < pos[pos_i] ? abs(r_diff) - 1 : pos[pos_i];
        }
        if(abs(r_diff) == abs(c_diff)){
            pos_i = r_diff > 0 ? (c_diff < 0 ? 1 : 3) : (c_diff < 0 ? 7 : 5);
            pos[pos_i] = abs(r_diff) - 1 < pos[pos_i] ? abs(r_diff) - 1 : pos[pos_i];
        }
    }
    
    int sum = 0;
    for(int p_i = 0; p_i < 8; p_i++){
        
        sum += pos[p_i];  
    } 
    printf("%d", sum);
    
    return 0;
}

Queen’s Attack II C++ Solution

#include <bits/stdc++.h>

using namespace std;

int n, k, x, y, xx, yy, ll=999999999, rr=999999999, ru=999999999, rd=999999999, lu=999999999, ld=999999999, res;
int uu=999999999    , dd=999999999;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    cin >> x >> y;
    for (int i=1;i<=k;i++)
    {
        cin >> xx >> yy;
        if (xx==x)
        {
            if (yy<y)
            {
                ll=min(y-yy-1, ll);
            }
            else
            {
                rr=min(rr, yy-y-1);
            }
        }
        else if (yy==y)
        {
            if (xx>x)
            {
                uu=min(uu, xx-x-1);
            }
            else
                dd=min(dd, x-xx-1);
        }
        else if (x+y==xx+yy || x-y==xx-yy)
        {
            if (xx>x && yy>y)
            {
                ru=min(ru, min(xx-x-1, yy-y-1));
            }
            else if (xx>x && yy<y)
            {
                rd=min(rd, min(xx-x-1, y-yy-1));
            }
            else if (xx<x && yy>y)
            {
                lu=min(lu, min(x-xx-1, yy-y-1));
            }
            else
            {
                ld=min(ld, min(x-xx-1, y-yy-1));
            }
        }
    }
    res+=min(ll, x-1);
    res+=min(rr, n-x);
    res+=min(uu, n-y);
    res+=min(dd, y-1);
    res+=min(ru, min(n-x, n-y));
    res+=min(rd, min(n-x, y-1));
    res+=min(lu, min(x-1, n-y));
    res+=min(ld, min(x-1, y-1));
    cout << res;
}

Queen’s Attack II C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    
    class Cell {
        public int Row;
        public int Col;
        
        public Cell(int r, int c) {
            Row = r;
            Col = c;
        }
        
        public bool OnGrid(int size) {
            return Row >= 1 && Row <= size && Col >= 1 && Col <= size;
        }
        
        public override bool Equals(object other) {
            Cell otherCell = (Cell)other;
            if (null == otherCell)    return false;
            
            return this.Row == otherCell.Row &&
                   this.Col == otherCell.Col;
        }
        
        public override int GetHashCode() {
            return 3 * Row.GetHashCode() + 7 * Col.GetHashCode();
        }
    }
    
    static void PrintGrid(int size, Cell queenCell, HashSet<Cell> moves, HashSet<Cell> obstacles) {
        Console.Write(" ");
        for (int col = 1; col <= size; col++) {
            Console.Write(col);
        }
        Console.WriteLine();
        
        for (int row = size; row >= 1; row--) {
            Console.Write(row);
            for (int col = 1; col <= size; col++) {
                Cell current = new Cell(row, col);
                
                if (current.Equals(queenCell))    Console.Write("Q");
                else if (moves.Contains(current))   Console.Write("*");
                else if (obstacles.Contains(current))   Console.Write("X");
                else Console.Write("O");
            }
            Console.WriteLine();
        }
    }

    static void Main(String[] args) {
        string[] tokens_n = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(tokens_n[0]);
        int k = Convert.ToInt32(tokens_n[1]);
        string[] tokens_rQueen = Console.ReadLine().Split(' ');
        int rQueen = Convert.ToInt32(tokens_rQueen[0]);
        int cQueen = Convert.ToInt32(tokens_rQueen[1]);
        
        HashSet<Cell> result = new HashSet<Cell>();
        HashSet<Cell> obstacles = new HashSet<Cell>();
        Cell queenCell = new Cell(rQueen, cQueen);
        
        for(int a0 = 0; a0 < k; a0++){
            string[] tokens_rObstacle = Console.ReadLine().Split(' ');
            int rObstacle = Convert.ToInt32(tokens_rObstacle[0]);
            int cObstacle = Convert.ToInt32(tokens_rObstacle[1]);
            
            Cell current = new Cell(rObstacle, cObstacle);
            obstacles.Add(current);
        }
        
        
        
        for (int row = rQueen - 1; row >= 1; row--) {
            Cell current = new Cell(row, cQueen);
            if (obstacles.Contains(current)) break;
            
            result.Add(current);
        }
        for (int row = rQueen + 1; row <= n; row++) {
            Cell current = new Cell(row, cQueen);
            if (obstacles.Contains(current)) break;
            
            result.Add(current);
        }
        for (int col = cQueen - 1; col >= 1; col--) {
            Cell current = new Cell(rQueen, col);
            if (obstacles.Contains(current)) break;
            
            result.Add(current);
        }
        for (int col = cQueen + 1; col <= n; col++) {
            Cell current = new Cell(rQueen, col);
            if (obstacles.Contains(current)) break;
            
            result.Add(current);
        }
        
        // Up Right
        for (int radius = 1; radius <= Math.Min(n - rQueen, n - cQueen); radius++) {
            Cell current = new Cell(rQueen + radius, cQueen + radius);
            if (obstacles.Contains(current) || !current.OnGrid(n)) break;
            
            result.Add(current);
        }
        // Down Right
        for (int radius = 1; radius <= Math.Min(rQueen, n - cQueen); radius++) {
            Cell current = new Cell(rQueen - radius, cQueen + radius);
            if (obstacles.Contains(current) || !current.OnGrid(n)) break;
            
            result.Add(current);
        }
        // Up Left
        for (int radius = 1; radius <= Math.Min(n - rQueen, cQueen); radius++) {
            Cell current = new Cell(rQueen + radius, cQueen - radius);
            if (obstacles.Contains(current) || !current.OnGrid(n)) break;
            
            result.Add(current);
        }
        // Down Left
        for (int radius = 1; radius <= Math.Min(rQueen, cQueen); radius++) {
            Cell current = new Cell(rQueen - radius, cQueen - radius);
            if (obstacles.Contains(current) || !current.OnGrid(n)) break;
            
            result.Add(current);
        }
        
        
        //PrintGrid(n, queenCell, result, obstacles);
        
        Console.WriteLine(result.Count);
    }
}

Queen’s Attack II Java Solution

import java.io.*;
import java.util.*;
import java.util.stream.*;
import static java.util.stream.Collectors.toList;

class Coordinates {
    public final int x;
    public final int y;

    public Coordinates(int _x, int _y) {
        x = _x;
        y = _y;
    }
}

class Reach {
    public int left;
    public int right;
    public int up;
    public int down;
    public int leftUp;
    public int rightUp;
    public int leftDown;
    public int rightDown;

    public Reach(int _left, int _right, int _up, int _down, int _leftUp, int _rightUp, int _leftDown, int _rightDown) {
        left = _left;
        right = _right;
        up = _up;
        down = _down;
        leftUp = _leftUp;
        rightUp = _rightUp;
        leftDown = _leftDown;
        rightDown = _rightDown;
    }

    public int sum() {
        return left + right + up + down + leftUp + rightUp + leftDown + rightDown;
    }
}

class Solver {

    private final int n;
    private final Coordinates queen;
    private final List<Coordinates> obstacles = new ArrayList<>();

    public Solver(int _n, int r_q, int c_q, List<List<Integer>> points) {
        n = _n;
        queen = new Coordinates(c_q, r_q);
        points.forEach(point -> {
            obstacles.add(new Coordinates(point.get(1), point.get(0)));
        });
    }

    public int solve() {
        int x_1 = queen.x - 1;
        int x_2 = n - queen.x;
        int y_1 = queen.y - 1;
        int y_2 = n - queen.y;

        Reach reach = new Reach(
                x_1, x_2, y_2, y_1, Math.min(x_1, y_2), Math.min(x_2, y_2), Math.min(x_1, y_1), Math.min(x_2, y_1)
        );

        obstacles.forEach(point -> {
            if (queen.y == point.y && queen.x > point.x) {
                reach.left = Math.min(reach.left, queen.x - point.x - 1);
            }
            if (queen.y == point.y && point.x > queen.x) {
                reach.right = Math.min(reach.right, point.x - queen.x - 1);
            }
            if (queen.x == point.x && point.y > queen.y) {
                reach.up = Math.min(reach.up, point.y - queen.y - 1);
            }
            if (queen.x == point.x && queen.y > point.y) {
                reach.down = Math.min(reach.down, queen.y - point.y - 1);
            }

            if (queen.x - point.x == point.y - queen.y && point.x < queen.x) {
                reach.leftUp = Math.min(reach.leftUp, queen.x - point.x - 1);
            }
            if (point.x - queen.x == point.y - queen.y && point.x > queen.x) {
                reach.rightUp = Math.min(reach.rightUp, point.x - queen.x - 1);
            }
            if (queen.x - point.x == queen.y - point.y && point.x < queen.x) {
                reach.leftDown = Math.min(reach.leftDown, queen.x - point.x - 1);
            }
            if (point.x - queen.x == queen.y - point.y && point.x > queen.x) {
                reach.rightDown = Math.min(reach.rightDown, point.x - queen.x - 1);
            }
        });

        return reach.sum();
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int n = Integer.parseInt(firstMultipleInput[0]);

        int k = Integer.parseInt(firstMultipleInput[1]);

        String[] secondMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int r_q = Integer.parseInt(secondMultipleInput[0]);

        int c_q = Integer.parseInt(secondMultipleInput[1]);

        List<List<Integer>> obstacles = new ArrayList<>();

        IntStream.range(0, k).forEach(i -> {
            try {
                obstacles.add(
                        Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                                .map(Integer::parseInt)
                                .collect(toList())
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        Solver solver = new Solver(n, r_q, c_q, obstacles);
        int result = solver.solve();

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Queen’s Attack II JavaScript Solution

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 obstacle = {};
    var dir = ['top','right','bottom','left','righttop','topleft','leftbottom','bottomright']
    for(var a0 = 0; a0 < k; a0++){
        var rObstacle_temp = readLine().split(' ');
        var rObstacle = parseInt(rObstacle_temp[0]);
        var cObstacle = parseInt(rObstacle_temp[1]);
        obstacle[rObstacle+'-'+cObstacle]=1;
        
    }
    var count = 0;
    var i;
    var top;
    var right;
    var bottom;
    var left;
 
            //'top')
              
                    for(i=rQueen+1;i<=n;i++)
                        {
                            if(obstacle[i+'-'+cQueen]==undefined)
                                count++;
                            else
                                break;
                        }
             
            //'right')
                
                    for(i=cQueen+1;i<=n;i++)
                        {
                            if(obstacle[rQueen+'-'+i]==undefined)
                                count++;
                            else
                                break;
                        }
                
            //'bottom')
                
                    for(i=rQueen-1;i>=1;i--)
                        {
                            if(obstacle[i+'-'+cQueen]==undefined)
                                count++;
                            else
                                break;
                        }
                
            //'left')
                
                    for(i=cQueen-1;i>=1;i--)
                        {
                            if(obstacle[rQueen+'-'+i]==undefined)
                                count++;
                            else
                                break;
                        }
    
                //'topright')
                
                top = rQueen+1;
                right = cQueen+1;
    
                while(top<=n&&right<=n)
                    {
                        if(obstacle[top+'-'+right]==undefined)
                                count++;
                            else
                                break;
                        top++;
                        right++;
                    }
                
        //'bottomright')
                
                bottom = rQueen-1;
                right = cQueen+1;
    
                while(bottom>=1&&right<=n)
                    {
                        if(obstacle[bottom+'-'+right]==undefined)
                                count++;
                            else
                                break;
                        bottom--;
                        right++;
                    }
                
          //'bottomleft')
                
                bottom = rQueen-1;
                left = cQueen-1;
    
                while(bottom>=1&&left>=1)
                    {
                        if(obstacle[bottom+'-'+left]==undefined)
                                count++;
                            else
                                break;
                        bottom--;
                        left--;
                    }
    
    //'topleft')
                
                top = rQueen+1;
                left = cQueen-1;
    
                while(top<=n&&left>=1)
                    {
                        if(obstacle[top+'-'+left]==undefined)
                                count++;
                            else
                                break;
                   
                top++;
                left--;
                    }
    process.stdout.write(count.toString())

}

Queen’s Attack II Python Solution

#!/bin/python3

import sys
import math

n,k = input().strip().split(' ')
n,k = [int(n),int(k)]
rQueen,cQueen = input().strip().split(' ')
rQueen,cQueen = [int(rQueen),int(cQueen)]
t=[]
g=0
for a0 in range(k):
    rObstacle,cObstacle = input().strip().split(' ')
    rObstacle,cObstacle = [int(rObstacle),int(cObstacle)]
    r,c=rQueen-rObstacle,cQueen-cObstacle
    if r==0 or c==0 or abs(r)==abs(c) :
        t+=[[rObstacle,cObstacle]]
r=1
while rQueen-r>0:
    if [rQueen-r,cQueen] not in t:
        g+=1
    else:
        break
    r+=1
r=1 

while rQueen+r<=n:
    if [rQueen+r,cQueen] not in t:
        g+=1
    else:
        break
    r+=1


c=1
while cQueen-c>0:
    if [rQueen,cQueen-c] not in t:
        g+=1
    else:
        break
    c+=1
c=1
while cQueen+c<=n:
    if [rQueen,cQueen+c] not in t:
        g+=1
    else:
        break
    c+=1

    
c,r=1,1
while cQueen-c>0 and rQueen-r>0:
    if [rQueen-r,cQueen-c] not in t:
        g+=1
    else:
        break
    c+=1
    r+=1
r,c=1,1
while cQueen+c<=n and rQueen+r<=n:
    if [rQueen+r,cQueen+c] not in t:
        g+=1
    else:
        break
    c+=1
    r+=1

c,r=1,1
while cQueen+c<=n and rQueen-r>0:
    if [rQueen-r,cQueen+c] not in t:
        g+=1
    else:
        break
    c+=1
    r+=1
c,r=1,1
while cQueen-c>0 and rQueen+r<=n:
    if [rQueen+r,cQueen-c] not in t:
        g+=1
    else:
        break
    c+=1
    r+=1

print(g)