1222. Queens That Can Attack the King

On an 8x8 chessboard, there can be multiple Black Queens and one White King.

Given an array of integer coordinates `queens` that represents the positions of the Black Queens, and a pair of coordinates `king` that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.

Example 1:

```Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
Output: [[0,1],[1,0],[3,3]]
Explanation:
The queen at [0,1] can attack the king cause they're in the same row.
The queen at [1,0] can attack the king cause they're in the same column.
The queen at [3,3] can attack the king cause they're in the same diagnal.
The queen at [0,4] can't attack the king cause it's blocked by the queen at [0,1].
The queen at [4,0] can't attack the king cause it's blocked by the queen at [1,0].
The queen at [2,4] can't attack the king cause it's not in the same row/column/diagnal as the king.
```

Example 2:

```Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
Output: [[2,2],[3,4],[4,4]]
```

Example 3:

```Input: queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]
Output: [[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]
```

Constraints:

• `1 <= queens.length <= 63`
• `queens[i].length == 2`
• `0 <= queens[i][j] < 8`
• `king.length == 2`
• `0 <= king[0], king[1] < 8`
• At most one piece is allowed in a cell.

1222. Queens That Can Attack the King
``````struct Solution;
use std::collections::HashSet;

type Point = Vec<i32>;

struct Chessboard {
directions: Vec<Point>,
queens: HashSet<Point>,
king: Point,
}

impl Chessboard {
fn new(queens_vec: Vec<Point>, king: Point) -> Self {
let directions: Vec<Point> = vec![
vec![1, 0],
vec![-1, 0],
vec![0, 1],
vec![0, -1],
vec![1, 1],
vec![-1, 1],
vec![1, -1],
vec![-1, -1],
];
let mut queens: HashSet<Point> = HashSet::new();
for queen in queens_vec {
queens.insert(queen);
}
Chessboard {
directions,
queens,
king,
}
}
fn contains(&self, point: &[i32]) -> bool {
point[0] >= 0 && point[1] >= 0 && point[0] < 8 && point[1] < 8
}
fn attack(&self, i: usize, step: i32) -> Point {
let direction = &self.directions[i];
let king = &self.king;
vec![king[0] + direction[0] * step, king[1] + direction[1] * step]
}
}

impl Solution {
fn queens_attackthe_king(queens: Vec<Vec<i32>>, king: Vec<i32>) -> Vec<Vec<i32>> {
let mut res = vec![];
let cb = Chessboard::new(queens, king);
for i in 0..8 {
let mut step = 1;
loop {
let p = cb.attack(i, step);
if cb.contains(&p) {
if cb.queens.contains(&p) {
res.push(p);
break;
} else {
step += 1;
}
} else {
break;
}
}
}
res
}
}

#[test]
fn test() {
let queens = vec_vec_i32![[0, 1], [1, 0], [4, 0], [0, 4], [3, 3], [2, 4]];
let king = vec![0, 0];
let mut res = vec_vec_i32![[0, 1], [1, 0], [3, 3]];
let mut ans = Solution::queens_attackthe_king(queens, king);
res.sort();
ans.sort();
assert_eq!(ans, res);
let queens = vec_vec_i32![[0, 0], [1, 1], [2, 2], [3, 4], [3, 5], [4, 4], [4, 5]];
let king = vec![3, 3];
let mut res = vec_vec_i32![[2, 2], [3, 4], [4, 4]];
let mut ans = Solution::queens_attackthe_king(queens, king);
res.sort();
ans.sort();
assert_eq!(ans, res);
let queens = vec_vec_i32![
[5, 6],
[7, 7],
[2, 1],
[0, 7],
[1, 6],
[5, 1],
[3, 7],
[0, 3],
[4, 0],
[1, 2],
[6, 3],
[5, 0],
[0, 4],
[2, 2],
[1, 1],
[6, 4],
[5, 4],
[0, 0],
[2, 6],
[4, 5],
[5, 2],
[1, 4],
[7, 5],
[2, 3],
[0, 5],
[4, 2],
[1, 0],
[2, 7],
[0, 1],
[4, 6],
[6, 1],
[0, 6],
[4, 3],
[1, 7]
];
let king = vec![3, 4];
let mut res = vec_vec_i32![[2, 3], [1, 4], [1, 6], [3, 7], [4, 3], [5, 4], [4, 5]];
let mut ans = Solution::queens_attackthe_king(queens, king);
res.sort();
ans.sort();
assert_eq!(ans, res);
}
``````