# leetcode 1222. Queens That Can Attack the King（python）

2022-01-31 15:54:47

「 This is my participation 11 The fourth of the yuegengwen challenge 16 God , Check out the activity details ：2021 One last more challenge

### describe

On an 8x8 chessboard, there can be multiple Black Queens and one White King.

Given an array of integer coordinates queens that represents the positions of the Black Queens, and a pair of coordinates king that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.

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 queen at [0,1] can attack the king cause they're in the same row.
The queen at [1,0] can attack the king cause they're in the same column.
The queen at [3,3] can attack the king cause they're in the same diagnal.
The queen at [0,4] can't attack the king cause it's blocked by the queen at [0,1].
The queen at [4,0] can't attack the king cause it's blocked by the queen at [1,0].
The queen at [2,4] can't attack the king cause it's not in the same row/column/diagnal as the king.
Copy code ``````

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]]
Copy code ``````

Example 3: ``````Input: 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]
Output: [[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]
Copy code ``````

Note:

``````1 <= queens.length <= 63
queens[i].length == 2
0 <= queens[i][j] < 8
king.length == 2
0 <= king, king < 8
At most one piece is allowed in a cell.
Copy code ``````

### analysis

According to the meaning , Give a 8x8 The chessboard of , There are many black queens and a white king . Given an array of integer coordinates representing the position of the black queen queens And a coordinate representing the position of the White King king , Return the coordinates of all queens who can attack the king （ In any order ）.

Although I haven't played this game , I don't know how the queen attacked the king , But after looking at the example, I basically understand , When the queen and the king are in the same column or row or diagonal and there are no other pieces in the middle , Then the queen can attack the king . It's easy to solve the problem if you know this , There are only four diagonals from top to bottom, left and right, a total of eight directions , Find the position of the first queen, record it in the result and return it .

``````class Solution(object):
def queensAttacktheKing(self, queens, king):
"""
:type queens: List[List[int]]
:type king: List[int]
:rtype: List[List[int]]
"""
result = []
x,y = king
# up
for r in range(x-1,-1,-1):
if [r,y] in queens:
result.append([r,y])
break
# down
for r in range(x+1, 8):
if [r,y] in queens:
result.append([r,y])
break

# left
for c in range(y-1,-1,-1):
if [x,c] in queens:
result.append([x,c])
break

# right
for c in range(y+1, 8):
if [x,c] in queens:
result.append([x,c])
break

tmp_x = x
tmp_y = y
# diagnal
for _ in range(8):
if tmp_x-1>=0 and tmp_y-1>=0 and [tmp_x-1,tmp_y-1] in queens:
result.append([tmp_x-1,tmp_y-1])
break
else:
tmp_x -= 1
tmp_y -= 1

tmp_x = x
tmp_y = y
# diagnal
for _ in range(8):
if tmp_x+1<8 and tmp_y+1<8 and [tmp_x+1,tmp_y+1] in queens:
result.append([tmp_x+1,tmp_y+1])
break
else:
tmp_x += 1
tmp_y += 1

tmp_x = x
tmp_y = y
# diagnal
for _ in range(8):
if tmp_x-1>=0 and tmp_y+1<8 and [tmp_x-1,tmp_y+1] in queens:
result.append([tmp_x-1,tmp_y+1])
break
else:
tmp_x -= 1
tmp_y += 1

tmp_x = x
tmp_y = y
# diagnal
for _ in range(8):
if tmp_x+1<8 and tmp_y-1>=0 and [tmp_x+1,tmp_y-1] in queens:
result.append([tmp_x+1,tmp_y-1])
break
else:
tmp_x += 1
tmp_y -= 1
return result

Copy code ``````

### Running results

``````Runtime: 28 ms, faster than 67.86% of Python online submissions for Queens That Can Attack the King.
Memory Usage: 13.4 MB, less than 75.00% of Python online submissions for Queens That Can Attack the King.
Copy code ``````

### analysis

Of course, the above solution is still too redundant , There are more ingenious solutions to the code , The core idea is the same as above , Find the position of the first queen from eight different directions and record it in the result , But the code is much simpler .

``````class Solution(object):
def queensAttacktheKing(self, queens, king):
"""
:type queens: List[List[int]]
:type king: List[int]
:rtype: List[List[int]]
"""
result = []
for i, j in [[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]]:
x, y = king
while 0 <= x < 8 and 0 <= y < 8:
x += i
y += j
if [x, y] in queens:
result.append([x, y])
break
return result
Copy code ``````

### Running results

``````Runtime: 28 ms, faster than 67.86% of Python online submissions for Queens That Can Attack the King.
Memory Usage: 13.3 MB, less than 92.86% of Python online submissions for Queens That Can Attack the King.
Copy code ``````