キングを攻撃できるクイーン

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
• 各セルには最大で一つの駒が配置できます。

解答:

class Solution:
    def isValid(self, x, y):
        if x < 0 or y < 0 or x >= 8 or y >= 8:
            return False
        return True

    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        x, y = king
        queens = set([tuple(q) for q in queens])
        op = []
        for dx, dy in [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]:
            n = 1
            while self.isValid(x + n * dx, y + n * dy):
                if (x + n * dx, y + n * dy) in queens:
                    op.append([x + n * dx, y + n * dy])
                    break
                n += 1
        return op

Enter fullscreen mode Exit fullscreen mode

こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。
https://dev.to/theabbie/queens-that-can-attack-the-king-3oeo