Placement of Blue Bridge Cup algorithm training vehicle Python 100 points

The first thought is state compression , Every row 、 There can only be one car in every train

set up n = 8, Then binary 11101010 Said in the first 2、4、6、7、8 There is one car at each position of the column

Put the car layer by layer in a row , Only one at a time , For example 6 Line can appear 00000000、00101011 wait , But it can't appear 11111111, According to this idea, the state should be layered first

for col in range(2 ** bord):
num = bin(col).count("1")
for idx in range(num, bord + 1):
state[idx][col] = 0
state[0][0] = 1
# The status of initialization not started is 1

With n=3 For example , Final state as follows ( For the convenience of presenting the results , Change to binary str, The practical application int)

initial :   {'000': 1}
The first 1 layer : {'000': 0, '100': 0}
The first 2 layer : {'000': 0, '100': 0, '110': 0, '101': 0}
The first 3 layer : {'000': 0, '100': 0, '110': 0, '101': 0, '111': 0}

The rule of state transition is ： Every line passed , The number of cars that can be added <= 1

So the judgment condition is ：

last_choose | cur_choose == cur_choose and bin(cur_choose - last_choose).count("1") <= 1

The first condition is used to eliminate ： similar last_choose = 010, cur_choose = 101 The situation of

The second condition is used to eliminate ： similar last_choose = 1100,cur_choose = 1111 The situation of , That is, adding 2 car (>1) vehicle

The code of the state transfer part is as follows

for row in range(1, bord + 1):
for cur_choose in state[row]:
# Traverse the status of the current row
val = 0
for last_choose in state[row - 1]:
# Traverse the conditions of the previous line
if last_choose | cur_choose == cur_choose and bin(cur_choose - last_choose).count("1") <= 1:
val += state[row - 1][last_choose]
# Accumulate the number of transferable States
state[row][cur_choose] = val
# assignment 

The above table is for you to proofread , Full marks end