_广度优先搜索.ppt

广度优先搜索,BFSBreadth-First-Search,队的定义：,队是特殊的线性表之一，它只允许在队的一端插入，在队的另一端删除。插入一端叫队尾（T），删除一端叫队首（H），没有任何元素的队叫做空队。队列遵循先进先出原则，排队购物、买票等，就是最常见的队。,队的定义：,队的基本操作,队的描述intq10000;inth,t;初始化h=t=1;注意此处q的变量类型，如果队列元素信息用整数来表示此处就用int如果元素是一个坐标则应该intq100002;或者用结构体,入队操作,voidenter(intx)qt=x;t+;把元素x入队，放到队尾,出队操作,voidout()qh=0;h+;我们定义的h变量，qh的值就是队首元素，通常我们使用完队首元素后，队首元素就应该马上出队,注意,队列的风格有很多种本文介绍的风格是把t位置预留出来，也就是qt永远是预留出来给下一个将要进队的元素当前队尾元素是qt-1;通常我们不会直接使用队尾元素而qh直接等于队首队列长度直接等于(t-h)t=h的时候代表队列为空,广度优先搜索,广度优先搜索类似于按层次遍历的过程。它和队有很多相似之处，运用了队的许多思想，其实就是对队的深入一步研究，它的基本操作和队列几乎一样。,举一个例子,从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。问最少经过多少城市,例子,方便大家理解，1表示能走，0表示不能走。这就是所谓邻接矩阵E100100;,我们使用队列思想,A为起点，最开始我们将A入队，标记A为”走过”我们定义一个数组z10000;如果zi为0则代表没走过对于位于队首的点，找出其直接相连而又没有走过的点设队首为qh用k循环一遍所有的点，看是否与A直接相连，又没有走过if(Eqhk=1并把点k标记为“走过”zk=zqh+1;这样zk肯定不会是0了K循环完了以后，队首就没用了，把它出队out();,#includeinti,j,k,l,m,n,a1000000;intE100100=1,0,0,1,1,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,1,1,0;intq10000;intz10000;inth,t;voidenter(intx)qt=x;t+;voidout()qh=0;h+;,main()z1=1;enter(1);while(h!=t)for(k=1;k=8;k+)if(Ehqk=1,1188-Giroro说不准迟到,这天开会，keroro又睡过头了。一看钟，离开会时间还有很短时间！必须在最短的时间内到达会议室！现在我们假定他处在一个二维地图上，其中keroro所在的坐标是（0,0），然后地图上有n个障碍物，即不能通过的点，坐标为（x,y），（-500=x,y=500）。会议室的坐标为（ex，ey），（-500=ex,ey=500）。在这个地图上keroro每一步只能移动相邻的4个点的坐标，且不穿直接穿过障碍物。如果他到达会议室的时间（即所走的步数）超过d（deadline），那么输出-1，否则输出keroro到达会议室所走的最少步数。假设至少存在一条路能到达会议室。,1188-Giroro说不准迟到,Input第一行为四个整数，n,d,ex,ey。(1=n=10000;0=d=1000;-500=ex,ey=500)第2行到第n+1行，每行两个整数x,y。(-500=x,y=500)Output如果keroro迟到则输出-1，否则输出keroro到会议室所走最少的步数。SampleInput7101202-13311142-1122SampleOutput-1Hint上述例子最少要11步，所以迟到了。,#includeinti,j,k,l,m,n,a10000;intc20002000;intq20000002,X,Y,z1,z2,z3,z4;inth,t;intfx42=0,1,0,-1,1,0,-1,0;voidenter(intx,inty)qt0=x