洛谷 -P3956-python-双端队列BFS

看到这道题前面的描述就想到了双端队列：

任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、 下、左、 右四个方向前进。

当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1个金币。

但是看到后面：

另外， 你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色

又觉得不行，这样就不符合“两端性”和单调性。

可是我只会用双端队列啊

所以既然是由于后面的描述出现问题，那就忽略他解决它。

可以这样，把花费0个金币和1个金币作为双端队列que的0和1。

至于花费两个金币的我们不管它，把它放到另一个队列que2里，因为BFS搜索的单调性可知这个队列里面逐渐放进去的也是单调的，每次从que中取出节点，把que2中花费等于该节点的节点取出放入que首部，这样就在整体上实现了单调性并且不会漏掉节点，当que空了就把这两个队列互换,于是可得如下代码：

from collections import defaultdict
from collections import deque
from itertools import permutations
from itertools import combinations
from math import *
from datetime import time
import sys
import heapq
sys.setrecursionlimit(6010)
m,n=map(int,input().split())
a=[[-1 for __ in range(m+1)]for _ in range(m+1)]
for i in range(n):
    x,y,c=map(int,input().split())
    a[x][y]=c
path=[[-1 for _ in range(m+1)]for i in range(m+1)]
d=[(-1,0),(1,0),(0,-1),(0,1)]
que=deque()
que2=deque()
que.append([1,1,0,1])
while que or que2:
    if not que:
        que,que2=que2,que
    now=que.popleft()
    while que2:
        now2=que2.popleft()
        if now[2]==now2[2]:
            que.appendleft(now2)
        else:
            que2.appendleft(now2)
            break
    if path[now[0]][now[1]]!=-1:
        continue
    path[now[0]][now[1]]=now[2]
    for k in range(4):
        after=[now[0]+d[k][0],now[1]+d[k][1]]
        if after[0]<1 or after[0]>m or after[1]<1 or after[1]>m or path[after[0]][after[1]]!=-1:
            continue
        if a[after[0]][after[1]]==-1:
            if now[3]==0:
                continue
            else:
                r=a[now[0]][now[1]] if len(now)==4 else now[4]
                after+=[now[2]+2,0,a[now[0]][now[1]]]
                que2.append(after)
        else:
            if a[now[0]][now[1]]==a[after[0]][after[1]] or(len(now)==5 and now[4]==a[after[0]][after[1]]):
                after+=[now[2],1]
                que.appendleft(after)
            else:
                after+=[now[2]+1,1]
                que.append(after)
print(path[m][m])