求求各位看下我的dfs为什么有绿有红还有紫
  • 板块P3392 涂国旗
  • 楼主ErgouTree
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/3/15 17:53
  • 上次更新2024/3/15 20:04:26
查看原帖
求求各位看下我的dfs为什么有绿有红还有紫
1216518
ErgouTree楼主2024/3/15 17:53

问题如上,我这个序列弄的应该是没啥问题,怎么就没过)),为什么还有re,是超数组了吗

n, m = map(int,input().split())
flag = []
for _ in range(n):
    row = list(map(str,input()))
    flag.append(row)
# 用来统计每行的颜色情况,列表元素里的列表分别表示有几个W(白),B(蓝),R(红)
colors_p = [[0]*3 for _ in range(n)]
for l in range(n):
    for r in range(m):
        if flag[l][r] == 'W':
            colors_p[l][0] += 1
        elif flag[l][r] == 'B':
            colors_p[l][1] += 1
        elif flag[l][r] == 'R':
            colors_p[l][2] += 1
# print(colors_p)
result = 10000000
# 标记已经搜索的情况
vis = [[0] * (m + 1) for _ in range(n + 1)]

# 最前面 x 行涂白色,最后面 y 行涂红色,要花费的最小代价为 g
def dfs(x,y,g):
    global result
    if x + y >= n:  # 超出边界
        return
    if vis[x][y]:  # 避免重复搜索,进行剪枝
        return

    vis[x][y] = 1
    dfs(x+1, y, g + (sum(m - colors_p[x][0] for _ in range(x))))
    dfs(x, y+1, g + (sum(m - colors_p[n-y-1][2] for _ in range(y+1))))
    if x + y < n and x > 0 and y > 0:
        ppl = sum(m - colors_p[i][1] for i in range(x,n-y))
        result = min(result, g + ppl)

dfs(0,0,0)
print(result)

2024/3/15 17:53
加载中...