数组练习 Leetcode 1222.可以攻击国王的王后

题目传送门：1222. 可以攻击国王的皇后?

在一个?下标从 0 开始?的?8 x 8?棋盘上，可能有多个黑皇后和一个白国王。

给你一个二维整数数组?queens，其中?queens[i] = [xQueeni, yQueeni]?表示第?i?个黑皇后在棋盘上的位置。还给你一个长度为?2?的整数数组?king，其中?king = [xKing, yKing]?表示白国王的位置。

返回?能够直接攻击国王的黑皇后的坐标。你可以以?任何顺序?返回答案。

示例 1：

输入：queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
输出：[[0,1],[1,0],[3,3]]
解释：上面的图示显示了三个可以直接攻击国王的皇后和三个不能攻击国王的皇后（用红色虚线标记）。

示例 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]]
解释：上面的图示显示了三个能够直接攻击国王的黑皇后和三个不能攻击国王的黑皇后（用红色虚线标记）。

提示：

• 1 <= queens.length < 64
• queens[i].length == king.length == 2
• 0 <= xQueeni, yQueeni, xKing, yKing < 8
• 所有给定的位置都是?唯一?的。

试题解析

题意：给一个国王结点的位置和若干个皇后结点，取国王的八个方向下，离其最近的皇后的位置

思路：

站在国王的角度下，向八个方位发送射线，找到每条射线第一个遇到的皇后的位置

• 使用direction二维数组，进行八个方位对应的位置的改变
• 使用isQueen二维数组，标记皇后的位置
• 对每一个射线的方位执行射线的延伸计算，直至超出坐标范围或者找到皇后

代码如下：

class Solution {
public:
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens,
                                            vector<int>& king) {
        // 八个方位，射线预备
        int direction[8][2] = {{1, 0},  {1, 1},   {0, 1},  {0, -1},
                               {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}};
        int isQueen[8][8];
        // 标记queen的位置
        for (auto& q : queens) {
            isQueen[q[0]][q[1]] = true;
        }
        vector<vector<int>> ans;
        for (auto& d : direction) {
            int x = king[0];
            int y = king[1];
            while (0 <= x && 0 <= y && x < 8 && y < 8) {
                if (isQueen[x][y]) {
                    // 满足遇到皇后的条件则将结点插入
                    ans.push_back({x, y});
                    // 结束当前射线
                    break;
                }
                // 循环进行射线的延伸
                x += d[0];
                y += d[1];
            }
        }
        return ans;
    }
};