Queen's Attack II

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 .

Constraints

• 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

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.

 php

<?php

// Complete the queensAttack function below.

function numberofPosition($n, $k, $x, $y,

$obstPosx, $obstPosy)

{

// d11, d12, d21, d22 are for diagnoal distances.

// r1, r2 are for vertical distance.

// c1, c2 are for horizontal distance.

$d11;

$d12;

$d21;

$d22;

$r1;

$r2;

$c1;

$c2;

// Initialise the distance to end of the board.

$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 each obstacle find the minimum distance.

// If obstacle is present in any direction,

// distance will be updated.

for ($i = 0; $i < $k; $i++)

{

if ( $x > $obstPosx[$i] && $y > $obstPosy[$i] &&

$x-$obstPosx[$i] == $y-$obstPosy[$i] )

$d11 = min($d11, $x-$obstPosx[$i]-1);

if ( $obstPosx[$i] > $x && $obstPosy[$i] > $y &&

$obstPosx[$i]-$x == $obstPosy[$i]-$y )

$d12 = min( $d12, $obstPosx[$i]-$x-1);

if ( $obstPosx[$i] > $x && $y > $obstPosy[$i] &&

$obstPosx[$i]-$x == $y-$obstPosy[$i] )

$d21 = min($d21, $obstPosx[$i]-$x-1);

if ( $x > $obstPosx[$i] && $obstPosy[$i] > $y &&

$x-$obstPosx[$i] == $obstPosy[$i]-$y )

$d22 = min($d22, $x-$obstPosx[$i]-1);

if ( $x == $obstPosx[$i] && $obstPosy[$i] < $y )

$r1 = min($r1, $y-$obstPosy[$i]-1);

if ( $x == $obstPosx[$i] && $obstPosy[$i] > $y )

$r2 = min($r2, $obstPosy[$i]-$y-1);

if ( $y == $obstPosy[$i] && $obstPosx[$i] < $x )

$c1 = min($c1, $x-$obstPosx[$i]-1);

if ( $y == $obstPosy[$i] && $obstPosx[$i] > $x )

$c2 = min($c2, $obstPosx[$i]-$x-1);

}

//echo $d11 ."\n" .$d12."\n".$d21. "\n". $d22. "\n" . $r1 . "\n" . $r2 . "\n" .$c1 . "\n" . $c2;

//exit;

return $d11 + $d12 + $d21 + $d22 + $r1 + $r2 + $c1 + $c2;

}

function queensAttack($n, $k, $r_q, $c_q, $obstacles) {

$key = [];

$value = [];

if(!empty($obstacles)) {

foreach($obstacles as $item) {

$key[] = $item[0];

$value[] = $item[1];

}

}

//print_r($key);

//exit;

return numberofPosition($n, $k, $r_q, $c_q, $key, $value);

}

$fptr = fopen(getenv("OUTPUT_PATH"), "w");

$stdin = fopen("php://stdin", "r");

fscanf($stdin, "%[^\n]", $nk_temp);

$nk = explode(' ', $nk_temp);

$n = intval($nk[0]);

$k = intval($nk[1]);

fscanf($stdin, "%[^\n]", $r_qC_q_temp);

$r_qC_q = explode(' ', $r_qC_q_temp);

$r_q = intval($r_qC_q[0]);

$c_q = intval($r_qC_q[1]);

$obstacles == array();

for ($i = 0; $i < $k; $i++) {

fscanf($stdin, "%[^\n]", $obstacles_temp);

$obstacles[] = array_map('intval',

preg_split('/ /', $obstacles_temp, -1, PREG_SPLIT_NO_EMPTY));

}

$result = queensAttack($n, $k, $r_q, $c_q, $obstacles);

fwrite($fptr, $result . "\n");

fclose($stdin);

fclose($fptr);