bfs单点多次扩散问题(简称hp问题)

解题思路:

注意事项:

参考代码:

# Python代码我还是补充一下八 

def bfs(queue,step):

    for i in queue:

        x,y=i

        for j in qu:

            a,b=j

            if 0<=x+a<n and 0<=y+b<n and list1[x+a][y+b]!="#":

                step,hp=temp[x][y]

                step+=1

                hp-=1

                if x+a==x1 and y+b==y1: # 到达终点

                    result[0]=min(result[0],step)

                if list1[x+a][y+b] =="%" and exist[x+a][y+b]: # 无敌时

                    exist[x+a][y+b]=0

                    temp[x+a][y+b]=[step,k]

                    queue.append([x+a,y+b])

                if list1[x+a][y+b]=="X" and hp>=0: # 陷阱

                    temp[x+a][y+b]=[step,hp]

                    queue.append([x+a,y+b])

                if list1[x+a][y+b]=="." :

                    if hp<0:# 走到.不扣血前提是之前没有遇到%

                        hp+=1

                    if hp>temp[x+a][y+b][1]:

                        queue.append([x+a,y+b])

                        temp[x+a][y+b]=[step,hp]

n,k=map(int,input().split())

list1=[]

for i in range(n):

    list1.append(list(input()))

exist=list([1]*n for i in range(n)) # 第一次经过的格子

temp=list([[0,-1]]*n for i in range(n)) # 存放step和hp

temp[0][0]=[0,0]

qu=[[0,1],[1,0],[0,-1],[-1,0]]

x1,y1=n-1,n-1 # 终点坐标

result=[10**6]

bfs([[0,0]],0)

if result==[10**6]:

    print(-1)

else:

    print(result[0])