会计学队列(duìliè)队列(duìliè)操作用队列实现图的宽度(kuāndù)优先搜索算法分析(fēnxī)voidbfs(v);//从v开始宽度有先遍历(biànlì)图{inicycque(q);//初始化队列qq.encycque(v);visted[v]:=true;//初始点v放入队列,并标号while(!q.empty)//直到队列不为空while(v的邻接顶点存在){q.encycque(v的邻接顶点);visted[v的邻接顶点]:=true;}q.dlcycque(v);}①已知队列(duìliè)(13,2,11,34,41,77,5,7,18,26,15),第一个进入队列(duìliè)的元素是13,则第五个出队列(duìliè)的元素是()。(NOIP9)A)5B)41C)77D)13E)18②设栈S和队列(duìliè)Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列(duìliè)Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为()。(NOIP8)A)2B)3C)4D)5【培训(péixùn)试题】细胞统计1611算法步骤：1、读入m*n矩阵,将其转换为0、1矩阵存入pic数组中；2、沿pic数组矩阵从上到下,从左到右,找到遇到的第一个细胞；将细胞的位置入队h,并沿其上、下、左、右四个方向搜索,如果遇到细胞(pic[i][j]=1)则将其位置入队,入队后的位置pic[i][j]数组置为0；3、将h队的队头出队,沿其上、下、左、右四个方向上搜索,如果遇到细胞则将其位置入队,入队后的位置pic数组置为0；4、重复3,直至h队空为止(wéizhǐ),则此时找出了一个细胞；5、重复2,直至矩阵找不到细胞；6、输出找到的细胞数。voidwork(intx,inty){intfirst,last,i,h,ll;first=1;last=1;total++;hang[1]=x;lie[1]=y;while(first<last){for(i=0;i<4;i++){h=hang[first]+dx[i];ll=lie[first]+dy[i];if(h>0&&h<=m&&ll>0&&ll<=n&&a[h][ll]){last++;hang[last]=h;lie[last]=ll;//入队(rùduì)a[h][ll]=false;}}first++;//出队}}intmain(){init();for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(a[i][j])work(i,j);cout<<total<<endl;}【培训试题(shìtí)】走迷宫2349【模拟(mónǐ)试题】最少步数18001、确定出发点从（x,y）出发通过一次广度优先搜索，可以找到从(x,y)至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的（x1，y1）和白马所在（x2，y2）到达(1,1)目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一样的。如果我们将终点(1,1)作为起点，这样只需要一次广度优先搜索便可以得到（x1，y1）和（x2，y2）到达(1,1)的最少步数。2、数据结构设queue—队列，存储从(1,1)可达的点（queue[k][1..2]）以及(yǐjí)到达该点所需要的最少步数（queue[k][3]）（0≤k≤192+1）。队列的首指针为open，尾指针为closed。初始时，queue中只有一个元素为(1,1)，最少步数为0。S—记录(1,1)到每点所需要的最少步数。显然，问题的答案是s[x1][y2]和s[x2][y2]。初始时，s[1][1]为0，除此之外的所有元素值设为-1。dx、dy—移动后的位置增量数组。马有12种不同的扩展方向：马走“日”：(x-2,y-1)(x-1,y-2)(x-2,y+1)(x-1,y+2)(x+2,y-1)(x+1,y-2)(x+2,y+1)(x+1,y+2)马走“田”：(x-2,y-2)(x-2,y+2)(x+2,y-2)(x+2,y+2)我们将i方向上的位置增量存入常量数组dx[i]、dy[i]中（1≤i≤12）intdx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2},dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};3、约束条件⑴不能越出界外。由于马的所有可能的落脚点s均在s的范围内，因此一旦马越出界外，就将其s值赋为0，表示(biǎoshì)“已经扩展过，且(1,1)到达其最少需要0步”。这看上去是荒