我们来考虑一下到底有多少状态, N*N(<=20*20)的地图, 蛇的长度是最大是L<=8,如果确定了蛇头的位置, 后面身体的每一段, 都可以用 {L,R,U,D} 来维护方向, 所以总的状态最多也就只有: 20*20*4^7 <= 7,000,000.

把每一个状态抽象为一个 结点, 可以得到一个有向图 G=(V,E), 其中点集大小 |V| <= 7,000,000, 边集大小 |E| <= 4*|V|, 所有边权都是1,

问题就变成了在 G 中求两点最短路径, 那当然 BFS 一次就可以啦. 这是普及组难度题呀各位.

AHdoc

队列我开300000才过。蒟蒻还是太弱了连搜索都不会……

BFS 队列要手动开到1e6 （巨坑）。