1222. Queens That Can Attack the King**

1222. Queens That Can Attack the King**

https://leetcode.com/problems/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.

Example1:

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.

还有几个例子见原网页吧.

C++ 实现 1

向 8 个方向分别搜索最近的 Queen. 思路来自 LeetCode 的 Submission.

class Solution {
private:void findQueensByDirection(const vector<vector<int>>& queens,const vector<int>& king,vector<vector<int>>& res,int i, int j) {int x = king[0], y = king[1];while (x >= 0 && x < 8 && y >= 0 && y < 8) {x += i;y += j;if (std::find(queens.begin(),queens.end(),vector<int>{x, y}) != queens.end()) {res.push_back({x, y});return;}}}
public:vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {vector<vector<int>> res;for (auto &i : {-1, 0, 1}) {for (auto &j : {-1, 0, 1}) {if (i == 0 && j == 0) continue;findQueensByDirection(queens, king, res, i, j);}}return res;}
};

C++ 实现 2

思路来自: [Python] Check 8 steps in 8 Directions, 检查 8 个方向的所有格子, 使用 Hash 表保存 Queens 的坐标, 判断 queen 是否在 Hash 表中.

class Solution {
private:// https://stackoverflow.com/questions/29855908/c-unordered-set-of-vectorsstruct VectorHash {size_t operator()(const std::vector<int>& v) const {std::hash<int> hasher;size_t seed = 0;for (int i : v) {seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);}return seed;}};
public:vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {unordered_set<vector<int>, VectorHash> records;vector<vector<int>> res;for (auto &p : queens) records.insert(p);for (auto &i : {-1, 0, 1}) {for (auto &j : {-1, 0, 1}) {for (auto &k : {1, 2, 3, 4, 5, 6, 7}) {int qx = king[0] + i * k, qy = king[1] + j * k;if (records.count({qx, qy})) {res.push_back({qx, qy});break;}}}}return res;}
};