Skip to content

1222. Queens That Can Attack the King 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens,
                                          vector<int>& king) {
    vector<vector<int>> ans;
    unordered_set<int> queensSet;

    for (vector<int>& queen : queens)
      queensSet.insert(hash(queen[0], queen[1]));

    vector<vector<int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
                                      {0, 1},   {1, -1}, {1, 0},  {1, 1}};
    for (vector<int> d : directions)
      for (int i = king[0] + d[0], j = king[1] + d[1];
           0 <= i && i < 8 && 0 <= j && j < 8; i += d[0], j += d[1])
        if (queensSet.contains(hash(i, j))) {
          ans.push_back({i, j});
          break;
        }

    return ans;
  }

 private:
  int hash(int i, int j) {
    return i * 8 + j;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
    List<List<Integer>> ans = new ArrayList<>();
    Set<Integer> queensSet = new HashSet<>();

    for (int[] queen : queens)
      queensSet.add(hash(queen[0], queen[1]));

    int[][] directions =
        new int[][] {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    for (int[] d : directions)
      for (int i = king[0] + d[0], j = king[1] + d[1]; 0 <= i && i < 8 && 0 <= j && j < 8;
           i += d[0], j += d[1])
        if (queensSet.contains(hash(i, j))) {
          ans.add(Arrays.asList(i, j));
          break;
        }

    return ans;
  }

  private int hash(int i, int j) {
    return i * 8 + j;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def queensAttacktheKing(self, queens: list[list[int]],
                          king: list[int]) -> list[list[int]]:
    ans = []
    queens = {(i, j) for i, j in queens}

    for d in [
        [-1, -1],
        [-1, 0],
        [-1, 1],
        [0, -1],
        [0, 1],
        [1, -1],
        [1, 0],
            [1, 1]]:
      i = king[0] + d[0]
      j = king[1] + d[1]
      while 0 <= i < 8 and 0 <= j < 8:
        if (i, j) in queens:
          ans.append([i, j])
          break
        i += d[0]
        j += d[1]

    return ans