力扣1222.可以攻击国王的王后

题目描述：

在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。

给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。

示例 1：

输入：queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]

输出：[[0,1],[1,0],[3,3]]

解释：

[0,1] 的皇后可以攻击到国王，因为他们在同一行上。

[1,0] 的皇后可以攻击到国王，因为他们在同一列上。

[3,3] 的皇后可以攻击到国王，因为他们在同一条对角线上。

[0,4] 的皇后无法攻击到国王，因为她被位于 [0,1] 的皇后挡住了。

[4,0] 的皇后无法攻击到国王，因为她被位于 [1,0] 的皇后挡住了。

[2,4] 的皇后无法攻击到国王，因为她和国王不在同一行/列/对角线上。示例 2：

输入：queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]

输出：[[2,2],[3,4],[4,4]]

示例 3：

输入：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]

输出：[[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]

提示：

• 1 <= queens.length <= 63
• queens[i].length == 2
• 0 <= queens[i][j] < 8
• king.length == 2

• 0 <= king[0], king[1] < 8
• 一个棋盘格上最多只能放置一枚棋子。

思路：

这个题有两种思路：

1、站在国王的角度，向八个方向延伸，遇到这个方向的第一个王后就停下来，标记一下这个方向已经搜到最近的皇后了，在存到答案里面就行了。

2、站在皇后的角度，遍历所有的皇后，查看当前皇后的坐标是否在国王的在八个方向上，如果是的，那么就再去比较当前皇后与上一个这个方向的皇后所在国王方向的距离，去一个最小值。

思路一呢比较通俗易懂，代码也比较容易实现，我这里也只给出这个思路的代码。

因为题目给的棋盘的范围比较小，每个方向遍历一次，在遍历这个方向的时候往外面扩张，类似于雷达，最多也就遍历7次，然后判断这个位置是否存在皇后，是的话就停下来就好了。这里皇后的位置可以用哈利表来存。

代码：

class Solution {
public:
    bool check(int x) {//判断坐标是否越界
        if (x >= 0 && x < 8)return true;
        return false;
    }
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        //给出八个方向行和列的偏移量
        int dx[8] = { -1,-1,-1,0,1,1,1,0 };
        int dy[8] = { -1,0,1,1,1,0,-1,-1 };
        int st[8] = { 0,0,0,0,0,0,0,0 };//初始化八个方向
        vector<vector<int>> ans;
        int x = king[0];
        int y = king[1];
        int g[10][10] = { 0 };//表示这个位置是否有皇后
        memset(g, 0, sizeof g);
        for (auto it : queens) {
            int a = it[0];
            int b = it[1];
            g[a][b] = 1;
        }
 
        for (int i = 0; i < 8; i++) {//遍历八个方向
            for (int j = 1; j <= 8 && check(x + dx[i] * j) && check(y + dy[i] * j); j++) {//j表示这个方向的距离
                if (!st[i] && g[x + dx[i] * j][y + dy[i] * j] == 1) {
                    st[i] = 1;//这个反向已经搜索过了
                    ans.push_back({ x + dx[i] * j,y + dy[i] * j });//存放答案
                }
            }
        }
        return ans;
    }
};

第二种思路的代码呢我就不写了，应该是可行的，我反正能过就行不管这么多了hhh.