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

「 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[0], king[1] < 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 .

answer

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 .

answer

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 

Original link ：leetcode.com/problems/qu…

Your support is my greatest motivation