标签:
难度: Hard
标签:
难度: Hard
运行时间: 2898 ms
内存: 257.0 MB
from collections import defaultdict class Solution: def getSchemeCount(self, n: int, m: int, chessboard: List[str]) -> int: if m > n: n, m = m, n chessboard = [list(x) for x in zip(*chessboard)] s, b, r, bb, rr, br, rb = 0, 1, 2, 3, 4, 5, 6 trans = { '.': {s: s, b: b, r: r, bb: bb, rr: rr, br: br, rb: rb}, 'R': {s: r, b: br, r: rr, rr: rr, rb: br}, 'B': {s: b, b: bb, r: rb, bb: bb, br: rb} } start = { '.': s, 'R': r, 'B': b } dp = {(i, j): defaultdict(int) for i in range(n) for j in range(m)} for i in range(n): for j in range(m): if chessboard[i][j] in start: chess_list = [chessboard[i][j]] else: chess_list = ['.', 'R', 'B'] if j == 0: if i == 0: for chess in chess_list: col_state = [0] * m row_state = start[chess] col_state[0] = row_state dp[(i, j)][(tuple(col_state), row_state)] = 1 else: pre = dp[(i - 1, m - 1)] cur = dp[(i, 0)] for chess in chess_list: row_state = start[chess] for (pre_col_state, _), pre_count in pre.items(): if pre_col_state[0] in trans[chess]: cur_col_state = list(pre_col_state) cur_col_state[0] = trans[chess][pre_col_state[0]] cur[(tuple(cur_col_state), row_state)] += pre_count else: pre = dp[(i, j - 1)] cur = dp[(i, j)] for chess in chess_list: for (pre_col_state, pre_row_state), pre_count in pre.items(): if pre_col_state[j] in trans[chess] and pre_row_state in trans[chess]: cur_col_state = list(pre_col_state) cur_col_state[j] = trans[chess][pre_col_state[j]] cur_row_state = trans[chess][pre_row_state] cur[(tuple(cur_col_state), cur_row_state)] += pre_count return sum(dp[(n - 1, m - 1)].values())
题解采用动态规划方法来解决问题。首先,如果列数大于行数,交换它们以简化处理。定义不同状态以表示棋盘上的可能配置,并使用一个转换字典来表明从一种状态到另一种状态的可能性。这些状态包括空格、放置黑棋、放置红棋、以及相邻位置上的不同棋子配置。使用一个二维字典dp存储每个位置的所有可能状态及其计数。遍历棋盘的每个格子,根据当前格子的内容(确定棋子、空或待定)更新dp数组。对于每个格子,考虑所有可能的棋子放置(如果当前是'?'则有三种可能),并基于前一个状态(上一个格子或上一行的结束)更新当前状态的计数。在行的开始和结束以及列的转换时需要特别处理。最后,所有在棋盘最后一个位置的状态计数之和即为答案。
时间复杂度: O(3^(n*m))
空间复杂度: O(3^(n*m))
from collections import defaultdict class Solution: def getSchemeCount(self, n: int, m: int, chessboard: List[str]) -> int: # 如果列数大于行数,转置棋盘以简化问题 if m > n: n, m = m, n chessboard = [list(x) for x in zip(*chessboard)] # 定义棋子状态 s, b, r, bb, rr, br, rb = 0, 1, 2, 3, 4, 5, 6 # 状态转换字典 trans = { '.': {s: s, b: b, r: r, bb: bb, rr: rr, br: br, rb: rb}, 'R': {s: r, b: br, r: rr, rr: rr, rb: br}, 'B': {s: b, b: bb, r: rb, bb: bb, br: rb} } # 初始化状态映射 start = { '.': s, 'R': r, 'B': b } # 初始化动态规划表 dp = {(i, j): defaultdict(int) for i in range(n) for j in range(m)} for i in range(n): for j in range(m): # 根据当前格子是否确定,设置可能的棋子列表 if chessboard[i][j] in start: chess_list = [chessboard[i][j]] else: chess_list = ['.', 'R', 'B'] # 特殊处理棋盘的起始位置 if j == 0: if i == 0: # 初始化棋盘的第一个格子 for chess in chess_list: col_state = [0] * m row_state = start[chess] col_state[0] = row_state dp[(i, j)][(tuple(col_state), row_state)] = 1 else: # 处理棋盘新的一行的起始格子 pre = dp[(i - 1, m - 1)] cur = dp[(i, 0)] for chess in chess_list: row_state = start[chess] for (pre_col_state, _), pre_count in pre.items(): if pre_col_state[0] in trans[chess]: cur_col_state = list(pre_col_state) cur_col_state[0] = trans[chess][pre_col_state[0]] cur[(tuple(cur_col_state), row_state)] += pre_count else: # 更新当前格子的状态 pre = dp[(i, j - 1)] cur = dp[(i, j)] for chess in chess_list: for (pre_col_state, pre_row_state), pre_count in pre.items(): if pre_col_state[j] in trans[chess] and pre_row_state in trans[chess]: cur_col_state = list(pre_col_state) cur_col_state[j] = trans[chess][pre_col_state[j]] cur_row_state = trans[chess][pre_row_state] cur[(tuple(cur_col_state), cur_row_state)] += pre_count # 返回可能的配置总数 return sum(dp[(n - 1, m - 1)].values())
在此题解中,状态转换字典`trans`通过详细地定义每种棋子在特定前状态下能够转换到的后状态来确保棋子之间的逻辑规则得以遵守,从而避免不合理的魔法共鸣现象。例如,状态字典中对于红棋'R'的定义是只能从空状态`s`转换到红棋状态`r`,从黑棋状态`b`转换到红黑相邻状态`br`等,这样的定义确保了棋子放置的合理性和规则的遵守。每种棋子和空格的可能状态转换都是根据棋盘规则事先定义好的,保证了算法的正确性和棋子间的合法互动。
解法中提到,对于棋盘上的`?`,可以选择放置空格、红棋或黑棋。这种方法确实覆盖了`?`位置可能的所有放置情况,因为按照题目的设定,棋盘上只有空格、红棋或黑棋这三种可能性。因此,这种处理方式没有遗漏任何特殊的放置情况,确保了对所有可能情况的全面考虑。
在处理棋盘的第一行和第一列时,特别关注了如何初始化棋盘的边界状态。如果是棋盘的起始格子,即第一行第一列的格子,根据题解代码,如果这个格子是`?`,则会考虑所有可能的棋子放置情况,包括空格、红棋和黑棋。对于每种可能的棋子,会初始化一个状态,这个状态代表了从棋盘开始到当前格子可能的状态配置。具体到代码实现,会为每种可能的棋子设置初始的状态映射,并在动态规划表`dp`中记录每种状态的计数。这样的处理确保了从棋盘的第一个格子开始,所有可能的状态都已被考虑和记录,为整个棋盘的状态转换提供了基础。