本文主要是介绍状态压缩动态规划 -- 棋盘问题 POJ 1321，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一个 N * N 的棋盘上面，有些格子不能放，放置 M 的棋子，
每两个棋子不能在同一行或者同一列，问有多少种放法
DFS太慢，用SCR好点点
Python 只有 22 行，其实可以更短，但是得排成很长很长的一行
while True:table = [ [ 0 for j in range( 300 ) ] for i in range( 12 ) ]table[0][0] = 1boardsize, chessnum = map( int, raw_input().split() ) if boardsize == chessnum == -1: breakstates = range( 1 << boardsize )cols = raws = range( 1, boardsize + 1 )chessboard = dict( zip( raws, [ ' ' + raw_input() for i in raws ] ) )ones = dict( zip( states, map( lambda s: str( bin( s ) ).count( '1' ), states ) ) )for raw in raws:for state in states:if ones[state] <= chessnum:table[raw][state] += table[raw - 1][state]for col in cols:s = 1 << ( col - 1 )if chessboard[raw][col] == '#' and state & s == 0:nextstate = state | stable[raw][nextstate] += table[raw - 1][state]print sum( [ table[boardsize][state] for state in states if ones[state] == chessnum ] )
这篇关于状态压缩动态规划 -- 棋盘问题 POJ 1321的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
