Hackerrank Queen's Attack II Solution
.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
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.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
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 .
Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
- 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 of the maximum score:
For of the maximum score:
Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
Print the number of squares that the queen can attack from position .
Sample Input 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} 4 04 4
Sample Output 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} 9
Explanation 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
The queen is standing at position on a chessboard with no obstacles:
Sample Input 1.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} 5 34 35 54 22 3
Sample Output 1.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} 10
Explanation 1.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
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.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} 1 01 1
Sample Output 2.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} 0
Explanation 2.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
Since there is only one square, and the queen is on it, the queen can move 0 squares.
Solution in java8
Approach 1.
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 rQueen = in.nextInt();
int cQueen = in.nextInt();
int up,left,right,down,uld,urd,dld,drd;
//set default from queen to each side
up = n-rQueen;
down = rQueen-1;
left = cQueen-1;
right = n-cQueen;
uld=up<left?up:left; //uoper left diagonal
urd=up<right?up:right; //upper right diagonal
dld=down<left?down:left;//down left diagonal
drd=down<right?down:right;//down right diagonal
for(int a0 = 0; a0 < k; a0++){
int rObstacle = in.nextInt();
int cObstacle = in.nextInt();
// your code goes here
if(cObstacle==cQueen){
//vertical
int path = Math.abs(rObstacle-rQueen)-1;
if(rQueen<rObstacle){
up=up<path?up:path;
}else{
down=down<path?down:path;
}
}else if(rObstacle==rQueen){
//horizontal
int path = Math.abs(cObstacle-cQueen)-1;
if(cQueen<cObstacle){
right = right<path?right:path;
}else{
left=left<path?left:path;
}
}else{
int path = Math.abs(cObstacle-cQueen)-1;
int path2= Math.abs(rObstacle-rQueen)-1;
if(path==path2){
if(cQueen<cObstacle && rQueen<rObstacle){
//urd
urd=urd<path?urd:path;
}else if(cQueen>cObstacle && rQueen<rObstacle){
//uld
uld=uld<path?uld:path;
}else if(cQueen<cObstacle && rQueen>rObstacle){
//drd
drd=drd<path?drd:path;
}else{
dld=dld<path?dld:path;
}
}
}
}
int total = up+down+left+right+urd+uld+drd+dld;
System.out.println(total);
}
}
Approach 2.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
import javafx.util.Pair;
public class Solution {
static boolean containsObstacle(int[][] obstacles, int row, int col) {
// Naive implementation which takes O(k) to determine whether a cell contains an
// obstacle.
for(int k = 0; k < obstacles.length; k++) {
int obst_row = obstacles[k][0];
int obst_col = obstacles[k][1];
if (obst_row == row && obst_col == col) return true;
}
return false;
}
static boolean containsObstacle_set(Set<Pair<Integer, Integer>> obstacles, int row, int col){
return obstacles.contains(new Pair<>(row, col));
}
// Complete the queensAttack function below.
static int queensAttack(int n, int k, int r_q, int c_q, int[][] obstacles) {
Set<Pair<Integer, Integer>> obstacle_set = new HashSet<>();
for(int i = 0; i < obstacles.length; i++) {
obstacle_set.add(new Pair<>(obstacles[i][0], obstacles[i][1]));
}
// accumulator for number of attacked squares
int attacked_squares = 0;
int curr_col = c_q;
int curr_row = r_q;
for (int curr_x_step = -1; curr_x_step <= 1; curr_x_step++){
for(int curr_y_step = -1; curr_y_step <= 1; curr_y_step++) {
curr_col = c_q;
curr_row = r_q;
if (curr_x_step == 0 && curr_y_step == 0) continue;
while(curr_row <= n && curr_col <= n
&& curr_row > 0 && curr_col > 0
&&(!containsObstacle_set(obstacle_set, curr_row, curr_col))) {
// Should we count the current cell?
if (!(r_q == curr_row && c_q == curr_col)) {
attacked_squares++;
}
curr_row += curr_y_step;
curr_col += curr_x_step;
}
}
}
return attacked_squares;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nk = scanner.nextLine().split(" ");
int n = Integer.parseInt(nk[0]);
int k = Integer.parseInt(nk[1]);
String[] r_qC_q = scanner.nextLine().split(" ");
int r_q = Integer.parseInt(r_qC_q[0]);
int c_q = Integer.parseInt(r_qC_q[1]);
int[][] obstacles = new int[k][2];
for (int i = 0; i < k; i++) {
String[] obstaclesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int j = 0; j < 2; j++) {
int obstaclesItem = Integer.parseInt(obstaclesRowItems[j]);
obstacles[i][j] = obstaclesItem;
}
}
int result = queensAttack(n, k, r_q, c_q, obstacles);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
Approach 3.
/**
* Jeroen van der Meer sr.
* [email protected]
* (c)2018
*
* zo 1 jul. 2018
*
*/
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
/**
* @author jeroen
*
*/
public class Solution {
static int queensAttack(int n, int k, int r_q, int c_q, int[][] obstacles) {
int result = 0;
HashMap<Integer, List<Integer>> obstacleMap = createMap(obstacles);
result += horizontaal(n,obstacleMap, r_q - 1, c_q - 1);
result += vertikaal(n,obstacleMap, r_q - 1, c_q - 1);
result += diagonaal(n,obstacleMap, r_q - 1, c_q - 1);
return result;
}
private static HashMap<Integer, List<Integer>> createMap(int[][] obstacles) {
HashMap<Integer, List<Integer>> result = new HashMap<>();
for (int[] element : obstacles) {
if (element.length != 0) {
List<Integer> rij = result.getOrDefault(element[0] - 1, new ArrayList<Integer>());
rij.add(element[1] - 1);
result.put(element[0] - 1, rij);
}
}
return result;
}
private static int horizontaal(int size, HashMap<Integer, List<Integer>> obstacle, int r_q, int c_q) {
int result = 0;
int h = r_q - 1;
while (checkPosition(size, obstacle, h, c_q)) {
result++;
h--;
}
h = r_q + 1;
while (checkPosition(size, obstacle, h, c_q)) {
result++;
h++;
}
return result;
}
private static int vertikaal(int size, HashMap<Integer, List<Integer>> obstacle, int r_q, int c_q) {
int result = 0;
int v = c_q - 1;
while (checkPosition(size, obstacle, r_q, v)) {
result++;
v--;
}
v = c_q + 1;
while (checkPosition(size, obstacle, r_q, v)) {
result++;
v++;
}
return result;
}
private static int diagonaal(int size, HashMap<Integer, List<Integer>> obstacle, int r_q, int c_q) {
int result = 0;
int h = r_q - 1;
int v = c_q - 1;
while (checkPosition(size, obstacle, h, v)) {
result++;
h--;
v--;
}
h = r_q + 1;
v = c_q + 1;
while (checkPosition(size, obstacle, h, v)) {
result++;
h++;
v++;
}
h = r_q - 1;
v = c_q + 1;
while (checkPosition(size, obstacle, h, v)) {
result++;
h--;
v++;
}
h = r_q + 1;
v = c_q - 1;
while (checkPosition(size, obstacle, h, v)) {
result++;
h++;
v--;
}
return result;
}
private static boolean checkPosition(int size, HashMap<Integer, List<Integer>> obstacles, int x, int y) {
if (x < 0 || x >= size || y < 0 || y >= size)
return false;
if ( obstacles.getOrDefault(x, Collections.emptyList()).contains(y))
return false;
return true;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
try (BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")))) {
String[] nk = scanner.nextLine().split(" ");
int n = Integer.parseInt(nk[0]);
int k = Integer.parseInt(nk[1]);
String[] r_qC_q = scanner.nextLine().split(" ");
int r_q = Integer.parseInt(r_qC_q[0]);
int c_q = Integer.parseInt(r_qC_q[1]);
int[][] obstacles = new int[k][2];
for (int i = 0; i < k; i++) {
String[] obstaclesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int j = 0; j < 2; j++) {
int obstaclesItem = Integer.parseInt(obstaclesRowItems[j]);
obstacles[i][j] = obstaclesItem;
}
}
int result = queensAttack(n, k, r_q, c_q, obstacles);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
}
Solution in python3
Approach 1.
import sys
n,k = input().strip().split(' ')
n,k = [int(n),int(k)]
rQueen,cQueen = input().strip().split(' ')
rQueen,cQueen = [int(rQueen),int(cQueen)]
ObList = []
for a0 in range(k):
rObstacle,cObstacle = input().strip().split(' ')
rObstacle,cObstacle = [int(rObstacle),int(cObstacle)]
# your code goes here
ObList.append((rObstacle,cObstacle))
ObSet = set(ObList)
Delta = [(0,1),(1,1),(1,0),(0,-1),(-1,-1),(-1,0),(1,-1),(-1,1)]
Count = 0
for shift in Delta:
Pos = (rQueen,cQueen)
while Pos[0] + shift[0] >=1 and Pos[0] + shift[0] <= n and Pos[1] + shift[1] >=1 and Pos[1] + shift[1] <= n:
Pos = (Pos[0]+shift[0],Pos[1]+shift[1])
if Pos in ObSet:
break
Count += 1
print(Count)
Approach 2.
#!/bin/python3
import math
import os
import random
import re
import sys
# Complete the queensAttack function below.
def queensAttack(n, k, r_q, c_q, obstacles):
tot_tiles = 0
direction = [[1,1],[1,0],[0,1],[-1,-1],[-1,0],[0,-1],[-1,1],[1,-1]]
blocked = 0
obs = {}
if(obstacles):
for ob in obstacles:
obs[ob[0],ob[1]] = 1
for move in direction:
i, j = r_q, c_q
i += move[0]
j += move[1]
while(i<=n and j<=n and i>0 and j>0):
if((i,j) in obs):
break
else:
tot_tiles += 1
i += move[0]
j += move[1]
return tot_tiles
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nk = input().split()
n = int(nk[0])
k = int(nk[1])
r_qC_q = input().split()
r_q = int(r_qC_q[0])
c_q = int(r_qC_q[1])
obstacles = []
for _ in range(k):
obstacles.append(list(map(int, input().rstrip().split())))
result = queensAttack(n, k, r_q, c_q, obstacles)
fptr.write(str(result) + '\n')
fptr.close()
Approach 3.
#!/bin/python3
import math
import os
import random
import re
import sys
# added function
def move_queen(n, updated_row, updated_col, r , c, obstacles):
p = 0
while True:
r = updated_row(r)
c = updated_col(c)
key = (r - 1) * n + c
if (c < 1 or c > n or r < 1 or r > n) or (key in obstacles):
return p
p += 1
return p
# Complete the queensAttack function below.
def queensAttack(n, k, r_q, c_q, obs):
obstacles = {}
for b in obs:
obstacles[(b[0] - 1) * n + b[1]] = None
p = 0
dr = [-1, -1, -1, 0, 0 , 1 , 1,1]
dc = [0, -1, 1, 1, -1 , 0 , 1,-1]
for i in range(8):
p += move_queen(n, (lambda r: r + dr[i]), (lambda c: c + dc[i] ), r_q, c_q, obstacles)
return p
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nk = input().split()
n = int(nk[0])
k = int(nk[1])
r_qC_q = input().split()
r_q = int(r_qC_q[0])
c_q = int(r_qC_q[1])
obstacles = []
for _ in range(k):
obstacles.append(list(map(int, input().rstrip().split())))
result = queensAttack(n, k, r_q, c_q, obstacles)
fptr.write(str(result) + '\n')
fptr.close()
Solution in cpp
Approach 1.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
int rq,cq;
cin>>rq>>cq;
rq=n-rq;
cq=cq-1;
int r,c;
int der=n-cq-1,aba=n-rq-1, diag_der_arr=min(rq,n-cq-1), diag_der_aba=min(n-cq-1,n-rq-1);
int izq=cq ,arr=rq, diag_izq_aba=min(cq,n-rq-1), diag_izq_arr=min(cq,rq);
for(int i=0;i<k;i++)
{
cin>>r>>c;r=n-r;c=c-1;
if(r==rq){if(c>cq)der=min(der,c-cq-1);else izq=min(izq,cq-c-1);}
if(c==cq){if(r>rq)aba=min(aba,r-rq-1);else arr=min(arr,rq-r-1);}
if((r+c)==(rq+cq))
{
if(r<rq) diag_der_arr=min(diag_der_arr,min(rq-r-1,c-cq-1));
else diag_izq_aba=min(diag_izq_aba,min(r-rq-1,cq-c-1));
}
if((r-c)==(rq-cq))
{
if(r>rq) diag_der_aba=min(diag_der_aba,min(r-rq-1,c-cq-1));
else diag_izq_arr=min(diag_izq_arr,min(rq-r-1,cq-c-1));
}
}
int suma=der+aba+diag_der_arr+diag_der_aba+izq+arr+diag_izq_aba+diag_izq_arr;
// cout<<der<<" "<<aba<<" "<<diag_der_arr<<" "<<diag_der_aba<<" "<<izq<<" "<<arr<<" "<<diag_izq_aba<<" "<<diag_izq_arr;
cout<<suma<<"\n";
}Approach 2.
#include <bits/stdc++.h>
using namespace std;
#define IN(a,x,y) (a>=x && a<=y)
const int MAXOBS = 100000;
int N, K;
int ox[MAXOBS+10], oy[MAXOBS+10];
int val(int x, int y)
{
int i;
int d11,d12,d21,d22,r1,r2,c1,c2;
d11 = min( x-1, y-1 );
d12 = min( N-x, N-y );
d21 = min( N-x, y-1 );
d22 = min( x-1, N-y );
r1 = y-1;
r2 = N-y;
c1 = x-1;
c2 = N-x;
for(i=0; i<K; i++)
{
if( x>ox[i] && y>oy[i] && x-ox[i] == y-oy[i] ) d11 = min( d11, x-ox[i]-1 );
if( ox[i]>x && oy[i]>y && ox[i]-x == oy[i]-y ) d12 = min( d12, ox[i]-x-1 );
if( ox[i]>x && y>oy[i] && ox[i]-x == y-oy[i] ) d21 = min( d21, ox[i]-x-1 );
if( x>ox[i] && oy[i]>y && x-ox[i] == oy[i]-y ) d22 = min( d22, x-ox[i]-1 );
if( x == ox[i] && oy[i]<y ) r1 = min( r1, y-oy[i]-1 );
if( x == ox[i] && oy[i]>y ) r2 = min( r2, oy[i]-y-1 );
if( y == oy[i] && ox[i]<x ) c1 = min( c1, x-ox[i]-1 );
if( y == oy[i] && ox[i]>x ) c2 = min( c2, ox[i]-x-1 );
}
return d11 + d12 + d21 + d22 + r1 + r2 + c1 + c2;
}
int main(void)
{
int i,j,k,kase=0;
int x,y;
scanf("%d %d",&N, &K);
scanf("%d %d",&x, &y);
assert(IN(N,1,100000));
assert(IN(K,0,100000));
for(i=0; i<K; i++)
{
scanf("%d %d",&ox[i], &oy[i]);
assert(IN(ox[i],1,N) && IN(oy[i],1,N) && (ox[i]!=x || oy[i]!=y));
}
printf("%d\n",val(x, y));
return 0;
}Approach 3.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
int k;
cin >> n >> k;
int rQ;
int cQ;
cin >> rQ >> cQ;
int r=n+1,l=0,u=0,d=n+1,ur=0,ul=0,dr=n+1,dl=n+1;
int c=0;
for(int a0 = 0; a0 < k; a0++){
int rO;
int cO;
cin >> rO >>cO;
if(rO==rQ) {
if(cO>cQ)
r=min(r,cO);
else
l=max(l,cO);
}
else if(cO==cQ)
{
if(rO>rQ)
d=min(d,rO);
else
u=max(u,rO);
}
else if(rQ+cQ==rO+cO)
{
if(rO>rQ)
dl=min(dl,rO);
else
ur=max(ur,rO);
}
else if(rQ-cQ==rO-cO)
{
if(rQ<rO)
dr=min(dr,rO);
else
ul=max(ul,rO);
}
}
// cout<<r<<l<<d<<u<<ur<<ul<<dr<<dl<<endl;
if(rQ-1>0) c+=abs(rQ-u)-1;
if(rQ+1<=n) c+=abs(rQ-d)-1;
if(cQ+1<=n) c+=abs(cQ-r)-1;
if(cQ-1>0) c+=abs(cQ-l)-1;
if(ur!=0)
{ if(cQ+1<=n && rQ-1>0) c+=abs(rQ-ur)-1;}
else c+=min(rQ-1,n-cQ);
if(ul!=0)
{ if(rQ-1>0&&cQ-1>0) c+=abs(rQ-ul)-1;}
else c+=min(rQ-1,cQ-1);
if(dr!=n+1)
{if(rQ+1<=n&&cQ+1<=n) c+=abs(rQ-dr)-1;}
else c+=min(n-rQ,n-cQ);
if(dl!=n+1)
{if(rQ+1<=n&&cQ-1>0) c+=abs(rQ-dl)-1;}
else c+=min(n-rQ,cQ-1);
cout<<c<<endl;
return 0;
}