首页 > 代码库 > 状态压缩动态规划 -- 棋盘问题 POJ 1321
状态压缩动态规划 -- 棋盘问题 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] = 1 boardsize, chessnum = map( int, raw_input().split() ) if boardsize == chessnum == -1: break states = 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 | s table[raw][nextstate] += table[raw - 1][state] print sum( [ table[boardsize][state] for state in states if ones[state] == chessnum ] )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。