题目地址：https://leetcode.com/problems/queens-that-can-attack-the-king/
题目描述
Onan 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、 1<=queens.length<=63；
2、 queens[0].length==2；
3、 0<=queens[i][j]<8；
4、 king.length==2；
5、 0<=king[0],king[1]<8；
6、 Atmostonepieceisallowedinacell.；
题目大意
棋盘上有一个国王K，和若干个皇后Q，求哪些皇后能威胁到国王。
解题方法
遍历
注意皇后会挡住其他的皇后，所以只有和国王处在同一条线上的第一个皇后才是威胁。因此我们从国王位置开始向8个方向辐射状遍历，找到在8个方向上能遇到的第一个皇后即可。
使用了set判断当前遍历到的位置上是否有皇后，如果找到皇后，则放入结果中，并且不再遍历。
C++代码如下：
class Solution {
public:
vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
set<vector<int>> s(queens.begin(), queens.end());
vector<vector<int>> res;
for (auto& dir : dirs) {
vector<int> pos = king;
while (true) {
pos[0] += dir[0];
pos[1] += dir[1];
if (pos[0] < 0 || pos[0] >= 8 || pos[1] < 0 || pos[1] >= 8)
break;
if (s.count(pos)) {
res.push_back(pos);
break;
}
}
}
return res;
}
private:
vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发