题解采用动态规划方法来解决问题。首先，如果列数大于行数，交换它们以简化处理。定义不同状态以表示棋盘上的可能配置，并使用一个转换字典来表明从一种状态到另一种状态的可能性。这些状态包括空格、放置黑棋、放置红棋、以及相邻位置上的不同棋子配置。使用一个二维字典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())