python-矩阵计数

解题思路:

参考连接https://blog.csdn.net/shamansi99/article/details/116561214

这篇博客中写的很详细，大家可以去看看。

注意事项:

参考代码:

n,m = map(int,input().strip().split())  
  
statenum = 2**m  #记录所有状态数
state_allow = []  
for i in range(statenum):  
    temp = '{:0{}b}'.format(i,m)     #转化为m位的二进制数
    for j in range(m-2):             #判断状态是否符合条件 
        if temp[j] == temp[j+1] == temp[j+2] == '1':  
            break  
    else:  
        state_allow.append(i)  
  
dp = [[[0 for k in range(statenum)] for j in range(statenum)] for i in range(n)]  #建立动态数组，dp[i][j][k]表示第i行状态为j，#第i-1行状态为k时符合条件的矩阵数
  
for item in state_allow:   #动态数组初始化
    dp[0][item][0] = 1  
for i in range(1,n):       
    for j in state_allow:  
        for k in state_allow:  
            for p in state_allow:  
                if j & k & p == 0:  #判断是否存在同一列存在3个‘1’
                    dp[i][j][k] = dp[i][j][k] + dp[i-1][k][p]  
ans = 0  
for item in state_allow:  
    ans = ans + sum(dp[n-1][item])  
print(ans)