题目地址：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 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发