Make writing a habit together! This is the fifth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.
describe
There is an 8 x 8 chessboard containing n pieces (rooks, queens, or bishops). You are given a string array pieces of length n, where pieces[i] describes the type (rook, queen, or bishop) of the ith piece. In addition, you are given a 2D integer array positions also of length n, where positions[i] = [ri, ci] indicates that the ith piece is currently at the 1-based coordinate (ri, ci) on the chessboard.
When making a move for a piece, you choose a destination square that the piece will travel toward and stop on.
- A rook can only travel horizontally or vertically from (r, c) to the direction of (r+1, c), (r-1, c), (r, c+1), or (r, c-1).
- A queen can only travel horizontally, vertically, or diagonally from (r, c) to the direction of (r+1, c), (r-1, c), (r, c+1), (r, c-1), (r+1, c+1), (r+1, c-1), (r-1, c+1), (r-1, c-1).
- A bishop can only travel diagonally from (r, c) to the direction of (r+1, c+1), (r+1, c-1), (r-1, c+1), (r-1, c-1).
You must make a move for every piece on the board simultaneously. A move combination consists of all the moves performed on all the given pieces. Every second, each piece will instantaneously travel one square towards their destination if they are not already at it. All pieces start traveling at the 0th second. A move combination is invalid if, at a given time, two or more pieces occupy the same square.
Return the number of valid move combinations.
Notes:
- No two pieces will start in the same square.
- You may choose the square a piece is already on as its destination.
- If two pieces are directly adjacent to each other, it is valid for them to move past each other and swap positions in one second.
Example 1:
Input: pieces = ["rook"], positions = [[1,1]]
Output: 15
Explanation: The image above shows the possible squares the piece can move to.
Copy the codeExample 2:
Input: pieces = ["queen"], positions = [[1,1]]
Output: 22
Explanation: The image above shows the possible squares the piece can move to.
Copy the codeExample 3:
Input: pieces = ["bishop"], positions = [[4,3]]
Output: 12
Explanation: The image above shows the possible squares the piece can move to.
Copy the codeExample 4:
Input: pieces = ["rook","rook"], positions = [[1,1],[8,8]] Output: There are 15 moves for each rook which results in 15 * 15 = 225 move combinations. However, there are two invalid move combinations: - Move both rooks to (8, 1), where they collide. - Move both rooks to (1, 8), where they collide. Thus there are 225 - 2 = 223 valid move combinations. Note that there are two valid move combinations that would result in one rook at (1, 8) and the other at (8, 1). Even though the board state is the same, these two move combinations are considered different since the moves themselves are different.Copy the codeExample 5:
Input: pieces = ["queen","bishop"], positions = [[5,7],[3,4]] Output: There are 12 * 24 = 288 move combinations. However, there are several invalid move combinations: - If the queen stops at (6, 7), it blocks the bishop from moving to (6, 7) or (7, 8). - If the queen stops at (5, 6), it blocks the bishop from moving to (5, 6), (6, 7), or (7, 8). - If the bishop stops at (5, 2), it blocks the queen from moving to (5, 2) or (5, 1). Of the 288 move combinations, 281 are valid.Copy the codeNote:
- n == pieces.length
- n == positions.length
- 1 <= n <= 4
- pieces only contains the strings “rook”, “queen”, and “bishop”.
- There will be at most one queen on the chessboard.
- 1 <= xi, yi< = 8
- Each positions[i] is distinct.
parsing
There is an 8 x 8 chessboard containing n pieces (rook, queen or bishop). Given an array of strings pieces of length N, pieces[I] describes the type of the ith fragment (roo, queen, or bishop). In addition, a two-dimensional array of integer positions of length N is given, where positions[I] = [ri, ci] represents the coordinate starting from 1 (Ri, CI) on the board where the ith chess piece is currently located.
When a piece moves, you can select the target square on which the piece will move and stop:
- Cars can only move horizontally or vertically from (r, C) to (r+1, C), (R-1, C), (R, C +1), or (r, C-1)
- Queen only horizontal, vertical, or diagonal line from (r, c) to (r + 1, c), (r – 1, c), (r, c + 1), (r, c – 1), (c + r + 1, 1), (r + 1, c – 1), (c + r – 1, 1), (c – r – 1, 1)
- Bishop can only from the (r, c) to (r + 1, c + 1), (r + 1, c – 1), (r – 1 c + 1), (c – r – 1, 1) oblique line
Move each piece on the board at the same time. All the pieces start to move from the 0 second, all the pieces of the end of the move position of the total number of combinations. If two or more pieces occupy the same square at a given time, the move combination is invalid. Returns the number of valid movement combinations.
Note:
- No two pieces will start in the same square
- You can choose the square where the piece is located as the destination, that is, you can not go
- If two pieces are directly adjacent to each other, they can move and switch positions within a second
There are three kinds of chess pieces, and each kind of chess piece can move. There are two kinds of chess pieces to stop: out of bounds and collision. It then tells us how many combinations of faces there are on the board after moving (or not moving) the pieces. Check the restrictions and find that there are at most 4 pieces, and at most only one queen. The board is also very small, and the moving position of each piece is limited. For this kind of problem, it is obvious that the general direction is to use DFS to violently traverse all possible positions of all pieces and find out all possible combinations of chess faces. The key is some small tricks. If an n-bit is used to indicate the status of all pieces, with 1 indicating that they can still move and 0 indicating that they have stopped, as in 0110, then the second and third pieces are simply increded by 1 in their direction. In addition, you can use a hash method to save the combinations that have already occurred, which reduces a lot of unnecessary recursion.
answer
class Solution(object):
def __init__(self):
self.result = set()
self.dir = [[-1, 0], [1, 0], [0, -1], [0, 1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
self.N = 0
def countCombinations(self, pieces, positions):
"""
:type pieces: List[str]
:type positions: List[List[int]]
:rtype: int
"""
self.N = len(pieces)
for state in range(1 << (3 * self.N)):
flag = 1
dirs = [0] * self.N
for k in range(self.N):
d = (state >> (3 * k)) % 8
if pieces[k] == 'rook' and d > 3:
flag = 0
break
if pieces[k] == 'bishop' and d < 4:
flag = 0
break
dirs[k] = d
if flag:
self.dfs(positions, dirs, (1 << self.N) - 1)
return len(self.result) + 1
def dfs(self, positions, dirs, state):
subset = state
while subset>0:
pos2 = copy.deepcopy(positions)
flag = 1
for i in range(self.N):
if (subset >> i) & 1:
pos2[i][0] += self.dir[dirs[i]][0]
pos2[i][1] += self.dir[dirs[i]][1]
if pos2[i][0] < 1 or pos2[i][0] > 8:
flag = 0
break
if pos2[i][1] < 1 or pos2[i][1] > 8:
flag = 0
break
if flag == 0:
subset = (subset - 1) & state
continue
if self.duplicate(pos2):
subset = (subset - 1) & state
continue
hash = self.getMyHash(pos2)
if hash in self.result:
subset = (subset - 1) & state
continue
self.result.add(hash)
self.dfs(pos2, dirs, subset)
subset = (subset - 1) & state
def duplicate(self, pos):
for i in range(self.N):
for j in range(i + 1, self.N):
if pos[i] == pos[j]:
return True
return False
def getMyHash(self, pos):
result = 0
for i in range(self.N):
result = result * 10 + pos[i][0]
result = result * 10 + pos[i][1]
return result
Copy the codeThe results
Runtime: 5016 ms, Given Python online submissions for Number of Valid Move Combinations On Chessboard. Memory Usage: Each node in the Python online submission list provides a possible route for each node.Copy the codeOriginal link: leetcode.com/problems/nu…
Your support is my biggest motivation