没有白走的路，每一步都算数
题目：
已知有很多的地窖，每一个地窖中又藏着很多的地雷，每个地窖之间都存在着相连性，但是不是任意的地窖都是相连的，要求我们找出一次能够找到的所有地雷数最大的情况，并且输出此情况一次经过哪些地窖。输出的情况数在第一行，第二行为地雷数目。
输入描述：
第一行：
此行表示第一个地窖到最后一个地窖每个地窖中的地雷数目
第二行及接下俩n+1行:
第二行表示第一个地窖和其他地窖之间的连通性，如果连通则表示为1，如果没有连通则表示为0，例如 1 1 1 0 则表示第一个地窖和第二个地窖，第三个地窖，第四个地窖有连通性，与第五个地窖没有连通性。
样例输入：
5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1
输出描述：
输出两行数据：
第一行：1 3 4 5
第二行：27
即第一行为需要找到的地窖类型，第二行为总的地雷数目
算法描述：
本蒻蒻使用的是DFS，毕竟节点数目不是太多，直接暴力循环找到所有可能的路径中的地雷数目。
数据结构描述：
因为是dfs，每个结点之间是否有联系，可以用二维数组来存储，并且存储的二维数组是一个上三角矩阵，这样存储可以节省时间，当然也可以在for循环中改变循环的起始节点也可以。
dfs最大的疼点
下标是否正确对dfs的结果影响很大，编辑算法的过程中一定一定注意自己定义数据的下标。结果不然很乐观。
最后结果
因为组后的结果实在一个列表里面，需要单独写一个冒泡循环给结果排序。
ac代码：
import os
import sys
n = int(input())
a = [0] + list(map(int,input().split()))
G = [[]]
ans = []
for i in range(n-1):
G.append([0 for i in range(i)] + [1] + list(map(int,input().split())))
##print(G)
def dfs(i:int,n:int,res:int,s:str):
global ans
if i == n:
ans.append([res,s])
return
for x in range(i,n):
if G[i][x] == 1:
dfs(x+1,n,res+a[x+1],s+" "+ str(x+1))
else:
ans.append([res,s])
for i in range(1,n+1):
s = str(i)
dfs(i,n,a[i],s)
print(ans)
for i in range(len(ans)):
for j in range(i,len(ans)):
if ans[i][0] tmp = ans[i] ans[i] = ans[j] ans[j] = ans[i] ##print(ans) print(ans[0][1]) print(ans[0][0]) debug代码的过程： 山重水复疑无路，柳暗花明又一村！！！ 相关阅读
您阅读本篇文章共花了：
发表评论