大神的探险 之 寻找宝藏-题解--python DFS

解题思路:

注意事项:
    多组输入数据的处理
参考代码:

def dfs(x,y,t):

        global mintime,step
   
        if t > mintime :
            return
    
        if flag[x][y]=='A': ## 找到宝藏
        
            mintime=min(mintime,t)
            
            return
    
        for i in range(4):
            if (x+step[i][0]) >= 0 and (x+step[i][0]) <= n-1 and (y+step[i][1]) >= 0 and (y+step[i][1]) <= m-1 : ##没越界
                if flag[x+step[i][0]][y+step[i][1]] == 'E' and table[x+step[i][0]][y+step[i][1]] == 0: ##将是路 且 该点没有走过

                   table[x+step[i][0]][y+step[i][1]]=1 
                   dfs(x+step[i][0],y+step[i][1],t+1) 
                   table[x+step[i][0]][y+step[i][1]]=0

                if flag[x+step[i][0]][y+step[i][1]] == 'T' and table[x+step[i][0]][y+step[i][1]] == 0:##将遇到怪兽 且 该点没有走过

                    table[x+step[i][0]][y+step[i][1]]=1
                    dfs(x+step[i][0],y+step[i][1],t+1+1)
                    table[x+step[i][0]][y+step[i][1]]=0

                if flag[x+step[i][0]][y+step[i][1]] == 'A' and table[x+step[i][0]][y+step[i][1]] == 0:##将到达宝藏

                   table[x+step[i][0]][y+step[i][1]]=1
                   dfs(x+step[i][0],y+step[i][1],t+1)
                   table[x+step[i][0]][y+step[i][1]]=0
            


while True : ##处理多组数据
    n,m=map(int,input().split())
    flag=[]   
    table=[]                         ##标记某点是否走过
    step=[[1,0],[0,1],[-1,0],[0,-1]] ##可以走的四个方向
    x=0
    y=0

    mintime=float('inf')

    for i in range(n):
        flag.append(list(input()))
        table.append([0]*m)

    for i in range(n):               ## 找到人的出发位置
        for j in range(m):
            if flag[i][j]=='C':
                table[i][j]=1
                x=i
                y=j

    dfs(x,y,0)
    if mintime==float('inf') :
        print('Game Over!')
    else:
        print(mintime)