。
找到一个节点，不是目标就顺便把他的子节点加入到队列中，这个是一层一层的关系。永远是先找完第一层，再找第二层，所以可以实现最短路径，树会比较容易理解。但是注意，该记录不讨论权重。 在这个里面涉及几个结构，队列和字典，列表
初始化队列Q; 清除visited数组; Q =起点S; while(Q非空) { 取队首元素U;出队; if(U == 目标状态 && U在矩阵内) {…} 所有与U相邻且未被访问的状态入队; 标记U为已访问; }’’’
下过象棋的人都知道，马只能走’日’字形（包括旋转90°的日）， 现在想象一下，给你一个n行m列网格棋盘， 棋盘的左下角有一匹马， 请你计算至少需要几步可以将它移动到棋盘的右上角， 若无法走到，则输出-1. 如n=1，m=2,则至少需要1步；若n=1，m=3,则输出-1。
from collections import deque def bfs(m,n): dx = [2,1,-1,-2,-2,-2,1,2] dy = [1,2,2,1,-1,-2,-2,-1]#写所有走的方向 v={(x,y) : False for x in range(1,m+1) for y in range(1,n+1)}#建迷宫 v[(1, 1)] = True q = deque([(1, 1, 0)])#初始化队列Q;前两个表x,y后一个表步数，每个点都有这三个参量 while len(q) > 0: p=q.popleft()#回顾pop是返回并删除 print(p) for i in range(8): x=p[0]+dx[i] y=p[1]+dy[i] if x<1 or y<1 or x>m or y>n: continue if v[(x,y)]: continue v[(x,y)]=True#表示走过 q.append((x, y, p[2] + 1)) if x==m and y==n: return p[2] + 1 return -1 print(bfs(5,5))‘’‘在某知名游戏中,“闪现”是一个很有用的技能, 某天你在机缘巧合之下在现实生活中也学会了这个技能, 你目前处在坐标为 a的位置上,欲到坐标为 b 的地方去。 你在 1 秒钟内可以移动 1 个单位的距离, 当然也可以使用“闪现”使你目前的坐标翻倍。 输入 输入的数据有多组,每组数据包含两个以空格为分隔符的非负整数 a 和 b。 其中,0 ≤ a ≤ 100000 且 0 ≤ b ≤100000。 输出 输出你由 a 出发到达坐标 b 所需的最短时间,每组数据的输出占一行。 样例输入 5 17 10 20 样例输出 4 1’’’
from collections import deque def BFS2(): a,b=map(int,input().split( )) dx=[1,-1,0] v={x:0 for x in range(1,b+1)} v[a]=1 q = deque([(a,0)]) while len(q)>0: p=q.popleft() for i in range(3): if dx[i]==0: x=p[0]+p[0] else: x=p[0]+dx[i] if x<1 or x>b : continue if v[x] == 1: continue v[x] = 1 q.append((x, p[1] + 1)) if x == b: return p[1] + 1 return -1 print(BFS2())1、输入问题，input实现换行换输入，调用map函数，实现行多赋值 2、看题目一开始没有考虑翻倍问题 3、出错最严重，关于边界，两个错误，第一次是字典v[x],x 的取值范围忘记左闭右开，第二次是边界到底从哪里开始，到哪里结束弄错，0，1问题。
就是自己做记录用，别来扯侵删
