https://www.hackerrank.com/challenges/queens-attack-2/problem

A queen is standing on an nxn chessboard. The chessboard’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 on the board is denoted 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) and, in a single move, she can attack any square in any of the eight directions (left, right, up, down, or the four diagonals). In the diagram below, the green circles denote all the cells the queen can attack from (4,4):

There are $k$ obstacles on the chessboard preventing the queen from attacking any square that has an obstacle blocking the the queen’s path to it. For example, an obstacle at location $(3,5)$ in the diagram above would prevent 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_q,c_q)$.

**Input Format**

The first line contains two space-separated integers describing the respective values of $n$ (the side length of the board) and $k$ (the number of obstacles).

The next line contains two space-separated integers describing the respective values of $r_q$ and $c_q$, denoting the position of the queen.

Each line $i$ of the $k$ subsequent lines contains two space-separated integers describing the respective values $r_i$ of $c_i$ and , denoting the position of obstacle $i$.

**Constraints**

$ 0 leq n leq 100000$

$ 0 leq k leq 100000$

A single cell may contain more than one obstacle; however, it is guaranteed that there will never be an obstacle at position $(r_q,c_q)$ where the queen is located.

**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 $(4,4)$ on a $4$x$4$ chessboard with no obstacles:

We then print the number of squares she can attack from that position, which is $9$.

**My approach:**

Instead of iterating through every single point in the queens path as that will be resource intensive when n is very high, I went with separating the paths into 8 different directions (up left, up, up right, right, etc).

```
int u, d, l, r, ul, ur, dl, dr;
u = d = l = r = ul = ur = dl = dr = 0;
bool modified(8) = { false };
```

Than I checked if there is an obstacle in the path by checking if the queens x = obstacles x or queens y = obstacles y and if its on the vertical/horizontal path of the queens I would find the distance by calculating the delta – 1 and to find the diagonal points I know since the points either have to have a 1 or -1 slope to be in the queens path so I checked if |queen’s y – obstacle’s y| = |queen’s x – obstacle’s x| and if it is true than I find the delta between either the x or y as either work and if there is no obstacles I would just use the edge to find the distance. I only checks to see if obstacle was in path then calculate the possible points than mark the direction as solved so if it is unmarked than it means there is no obstacles in the path so I find the distance from edge using:

```
if (!modified(0)) u = n - qy;
if (!modified(1)) d = qy - 1;
if (!modified(2)) l = qx - 1;
if (!modified(3)) r = n - qx;
if (!modified(4) && qy != n && qx != 1) ul = (qx - 1 < n - qy) ? qx - 1 : n - qy;
if (!modified(5) && qy != n && qx != n) ur = (n - qx < n - qy) ? n - qx : n - qy;
if (!modified(6) && qy != 1 && qx != 1) dl = (qx - 1 < qy - 1) ? qx - 1 : qy - 1;
if (!modified(7) && qy != 1 && qx != n) dr = (n - qx < qy - 1) ? n - qx : qy - 1;
```

Sorry for messy style, this is my first time on stackoverflow/stackexchange.

Full code:

```
int queensAttack(const int &n, const int &k, const int & qy, const int & qx, const vector<vector<int>> &obstacles) {
int u, d, l, r, ul, ur, dl, dr;
u = d = l = r = ul = ur = dl = dr = 0;
bool modified(8) = { false };
for (int i = 0; i < obstacles.size(); i++) {
int temp{};
if (obstacles(i)(1) == qx) {
if (obstacles(i)(0) > qy) {
temp = obstacles(i)(0) - qy - 1;
if (modified(0) && u > temp) {
u = temp;
}
else if (!modified(0)) u = temp;
modified(0) = true;
}
else {
temp = qy - obstacles(i)(0) - 1;
if (modified(1) && d > temp) {
d = temp;
}
else if (!modified(1)) d = temp;
modified(1) = true;
}
}
if (obstacles(i)(0) == qy) {
if (obstacles(i)(1) < qx) {
temp = qx - obstacles(i)(1) - 1;
if (modified(2) && l > temp) {
l = temp;
}
else if (!modified(2)) l = temp;
modified(2) = true;
}
else {
temp = obstacles(i)(1) - qx - 1;
if (modified(3) && r > temp) {
r = temp;
}
else if (!modified(3)) r = temp;
modified(3) = true;
}
}
if (abs(qy - obstacles(i)(0)) == abs(qx - obstacles(i)(1))) {
if (obstacles(i)(0) > qy && obstacles(i)(1) < qx) {
temp = qx - obstacles(i)(1) - 1;
if (modified(4) && ul > temp) {
ul = temp;
}
else if (!modified(4)) ul = temp;
modified(4) = true;
}
if (obstacles(i)(0) > qy && obstacles(i)(1) > qx) {
temp = obstacles(i)(1) - qx - 1;
if (modified(5) && ur > temp) {
ur = temp;
}
else if (!modified(5)) ur = temp;
modified(5) = true;
}
if (obstacles(i)(0) < qy && obstacles(i)(1) < qx) {
temp = qx - obstacles(i)(1) - 1;
if (modified(6) && dl > temp) {
dl = temp;
}
else if (!modified(6)) dl = temp;
modified(6) = true;
}
if (obstacles(i)(0) < qy && obstacles(i)(1) > qx) {
temp = obstacles(i)(1) - qx - 1;
if (modified(7) && dr > temp) {
dr = temp;
}
else if (!modified(7)) dr = temp;
modified(7) = true;
}
}
}
if (!modified(0)) u = n - qy;
if (!modified(1)) d = qy - 1;
if (!modified(2)) l = qx - 1;
if (!modified(3)) r = n - qx;
if (!modified(4) && qy != n && qx != 1) ul = (qx - 1 < n - qy) ? qx - 1 : n - qy;
if (!modified(5) && qy != n && qx != n) ur = (n - qx < n - qy) ? n - qx : n - qy;
if (!modified(6) && qy != 1 && qx != 1) dl = (qx - 1 < qy - 1) ? qx - 1 : qy - 1;
if (!modified(7) && qy != 1 && qx != n) dr = (n - qx < qy - 1) ? n - qx : qy - 1;
return u + d + l + r + ul + ur + dl + dr;
```

}

Forgot to mention I loop through the obstacles and only replaces the current distance if the new one is smaller as the obstacles in the array aren’t in order from closest to farthest.