题解 | 小红的矩阵修改

import sys

i = 0
s = []
n, m = 0, 0
for line in sys.stdin:
    if i == 0:
        n, m = map(int, line.split())
    else:
        s.append(line[:-1])
    i += 1
val = {
    "r": 0,
    "e": 1,
    "d": 2
}
all_col = []
def check(a, b, n):
    for i in range(n):
        if a % 10 == b % 10:
            return False
        a //= 10
        b //= 10
    return True
def change_num(col, a):
    res = 0
    for i in range(len(col) - 1, -1, -1):
        if a % 10 != col[i]:
            res += 1
        a //= 10
    return res
def get_all_col(x, i, a):
    global all_col
    for j in range(3):
        if i == 1:
            a = j
            if i == x:
                all_col.append(a)
            else:
                get_all_col(x, i + 1, a)
        else:
            if a % 10 == j:
                continue
            else:
                b = a * 10 + j
                if i == x:
                    all_col.append(b)
                else:
                    get_all_col(x, i + 1, b)
get_all_col(n, 1, 0)
# print(all_col)
dp = [[0] * len(all_col) for _ in range(m)]

for i in range(m):
    for j in range(len(all_col)):
        col = [val[s[k][i]] for k in range(n)]
        if i == 0:
            dp[i][j] = change_num(col, all_col[j])
        else:
            for k in range(len(all_col)):
                if check(all_col[j], all_col[k], n):
                    dp[i][j] = min(dp[i][j], change_num(col, all_col[j]) + dp[i - 1][k]) if dp[i][j] != 0 else change_num(col, all_col[j]) + dp[i - 1][k]
res = dp[m - 1][0]
for i in range(len(all_col)):
    res = min(res, dp[m - 1][i])
print(res)


        

• 首先获取每列可能的red组合情况，共pow(3,n)种，筛选出相邻元素不同的所有情况all_col，得到可能的情况数为len(all_col)
• 按列动态规划，dp的维度为(m, len(all_col))，对于每列的每种情况，得到前一列的所有序列与当前列的某一序列a不冲突的序列最小值加上当前列的元素变为情况a的修改步数即为当前列变为序列a的最小步数