“This is the 16th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

On an 8×8 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], [2, 4]], king = [0, 0] Output: [[0, 1], [1, 0], [3]] Explanation: The queen at [0,1] can attack The king cause they're in The same row 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 the code

Example 2:

Input: queens = [[0, 0], [1, 1], [2], [3, 4], [3, 5], [4], [4, 5]], king = [3, 3] Output: [[2], [3, 4], [4]]Copy the 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], [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] the Output: [[2, 3], [1, 4], [1, 6], [3, 7], [4, 3], [5, 4], [4, 5]]Copy the 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 the code

parsing

An 8×8 chessboard with multiple black queens and a white king is given. Given an integer coordinate array queens representing the position of the black Queen and a coordinate king representing the position of the white King, return the coordinates of all queens that can attack the king, in any order.

Although I haven’t played this game, I don’t know how the queen attacks the king, but AFTER seeing the example, I basically understand that when the queen and the king are in the same column or row or diagonal line and there are no other pieces in the middle, the queen can attack the king. If you know this, you can easily solve the problem. You just need to find the position of the first queen in eight directions, from top, bottom, left, and four diagonals, and 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 the code

The results

Given the linked submissions in Python online submissions That Can Attack the King. Submissions in Python online submissions for Queens That Can Attack the King.Copy the code

parsing

Of course, the above solution is still too redundant, there is a more clever code solution, the core idea is the same as above, from eight different directions to find the position of the first queen recorded 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 the code

The results

Given the linked submissions in Python online submissions That Can Attack the King. Submissions in Python online submissions for Queens That Can Attack the King.Copy the code

Original link: leetcode.com/problems/qu…

Your support is my biggest motivation