1222.可以攻击国王的皇后

链接：1222.可以攻击国王的皇后
难度：Medium
标签：数组、矩阵、模拟
简介：在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。

题解 1 - cpp

• 编辑时间：2023-09-14
• 执行用时：8ms
• 内存消耗：10.97MB
• 编程语言：cpp
• 解法介绍：方向数组遍历。

vector<vector<int>> dirs2 = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
class Solution {
public:
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        vector<vector<bool>> board(8, vector<bool>(8, false));
        for (auto &q : queens) board[q[0]][q[1]] = true;
        vector<vector<int>> res;
        auto check = [&](vector<int> pos, vector<int> &dir) {
            for (int i = 1; i < 8; i++) {
                pos[0] += dir[0];
                pos[1] += dir[1];
                if (0 <= pos[0] && pos[0] < 8 && 0 <= pos[1] && pos[1] < 8) {
                    if (board[pos[0]][pos[1]]) {
                        res.push_back(pos);
                        return;
                    }
                } else return;
            }
        };
        for (auto &d : dirs2) check(king, d);
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-09-14
• 执行用时：40ms
• 内存消耗：16MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        dirs2 = [(0, 1), (0, -1), (1, 0), (-1, 0),
                    (1, 1), (1, -1), (-1, 1), (-1, -1)]
        board = [[False for j in range(8)] for i in range(8)]
        for [x, y] in queens:
            board[x][y] = True
        res = []
        for i in range(1, 8):
            if not dirs2: break
            for j in range(len(dirs2) - 1, -1, -1):
                x = king[0] + dirs2[j][0] * i
                y = king[1] + dirs2[j][1] * i
                if 0 <= x < 8 and 0 <= y < 8:
                    if board[x][y]:
                        res.append([x, y])
                        dirs2.remove(dirs2[j])
                else:
                    dirs2.remove(dirs2[j])
        return res

题解 3 - python

• 编辑时间：2023-09-14
• 执行用时：48ms
• 内存消耗：15.65MB
• 编程语言：python
• 解法介绍：同上。

dirs = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    class Solution:
        def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
            board = [[False for j in range(8)] for i in range(8)]
            for [x, y] in queens:
                board[x][y] = True
            res = []
            def check(pos: List[int], dir: List[int]) -> bool:
                for _ in range(1, 8):
                    pos[0] += dir[0]
                    pos[1] += dir[1]
    
                    if 0 <= pos[0] < 8 and 0 <= pos[1] < 8:
                        if board[pos[0]][pos[1]]:
                            res.append([pos[0], pos[1]])
                            return 
                    else:
                        return
            for d in dirs:
                check(list(king), d)
            return res

题解 4 - rust

• 编辑时间：2023-09-14
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

pub const DIRS2: [[i32; 2]; 8] = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
    [1, 1],
    [1, -1],
    [-1, 1],
    [-1, -1],
];
impl Solution {
    pub fn queens_attackthe_king(queens: Vec<Vec<i32>>, king: Vec<i32>) -> Vec<Vec<i32>> {
        let mut board = vec![vec![false; 8]; 8];
        for queen in queens {
            board[queen[0] as usize][queen[1] as usize] = true;
        }
        let mut res = vec![];
        let mut check = |mut pos: Vec<usize>, dir: &[i32]| {
            for i in 1..8 {
                let x = pos[0] as i32 + dir[0] * i;
                let y = pos[1] as i32 + dir[1] * i;
                if 0 <= x && x < 8 && 0 <= y && y < 8 {
                    if board[x as usize][y as usize] {
                        res.push(vec![x, y]);
                        return;
                    }
                } else {
                    return;
                }
            }
        };
        for d in &DIRS2 {
            check(king.iter().map(|v| *v as usize).collect(), d);
        }
        res
    }
}