On a 0-indexed 8 x 8
chessboard, there can be multiple black queens ad one white king.
You are given a 2D integer array queens
where queens[i] = [xQueeni, yQueeni]
represents the position of the ith
black queen on the chessboard. You are also given an integer array king
of length 2
where king = [xKing, yKing]
represents the position of the white king.
Return the coordinates of the black queens that can directly attack the king. You may return the answer in any order.
Example 1:
Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0] Output: [[0,1],[1,0],[3,3]] Explanation: The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).
Example 2:
Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3] Output: [[2,2],[3,4],[4,4]] Explanation: The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).
Constraints:
1 <= queens.length < 64
queens[i].length == king.length == 2
0 <= xQueeni, yQueeni, xKing, yKing < 8
- All the given positions are unique.
可以攻击国王的皇后。
在一个 8x8 的棋盘上,放置着若干「黑皇后」和一个「白国王」。
给定一个由整数坐标组成的数组
queens
,表示黑皇后的位置;以及一对坐标king
,表示白国王的位置,返回所有可以攻击国王的皇后的坐标(任意顺序)。
又是一道在棋盘上的模拟题。注意题目要求,需要返回的是在与国王分别在同一行,同一列,同一条对角线上的能最先攻击到国王的皇后的坐标。有几个地方题目没有点出,比如在同一行(同一列或者同一条对角线也是同理)上,国王的左边和右边各有一个与国王距离相等的皇后,那么这两个皇后都需要被记录。
具体做法是我先用一个二维 boolean 数组记录棋盘上所有皇后的位置,标记为 true。然后从国王的位置开始,往八个方向延伸(这是皇后能走的方向),在每个方向上只要遇到皇后就停下并把皇后的坐标加入结果集。
时间O(1) - 8x8
空间O(1) - 8x8
Java实现
1 class Solution { 2 public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) { 3 List<List<Integer>> res = new ArrayList<>(); 4 boolean[][] board = new boolean[8][8]; 5 for (int[] q : queens) { 6 int qx = q[0]; 7 int qy = q[1]; 8 board[qx][qy] = true; 9 } 10 11 int[][] dirs = new int[][] {{-1, 0}, {-1, 1}, {-1, -1}, {0, 1}, {0, -1}, {1, 0}, {1, 1}, {1, -1}}; 12 for (int[] dir : dirs) { 13 int x = king[0] + dir[0]; 14 int y = king[1] + dir[1]; 15 while (x >= 0 && x < 8 && y >= 0 && y < 8) { 16 if (board[x][y] == true) { 17 res.add(Arrays.asList(x, y)); 18 break; 19 } 20 x += dir[0]; 21 y += dir[1]; 22 } 23 } 24 return res; 25 } 26 }
标签:king,King,int,attack,Attack,皇后,Queens,dir,queens From: https://www.cnblogs.com/cnoodle/p/17706256.html