90队列

数据结构——队列与广搜1队列的定义所谓队列，就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针w指向队尾元素，即w总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针t指向排头元素。初始时t=w=0（如下图）。3265419队列头t队列尾w当tw时,队列空；W-t=m时，队列满队列数组a下标：1234567……我们按照如下方式定义队列：Constm=队列元素的上限；Typeequeue=array[1…m]ofqtype；{队列的类型定义}Varq：equeue；{队列}t，w：integer；{队尾指针和队首指针}2、队列的基本运算队列的运算主要有两种：入队（aDD）和出队（DEL）1、过程ADD(x)—在队列q的尾端插入元素xprocedureADD(x：qtyper)；begin{后移队尾指针并插入元素x}w:=w+1；q[w]←x；end；{ADD}2、函数DEL—取出q队列的队首元素functionDEL；begin{取出队首元素并后移队首指针}del:=q[t]；t:=t+1;end；{DEL}假溢出由于队列只能在一端插入，在另一端删除，因此随着入队及出队运算的不断进行，就会出现一种有别于栈的情形：队列在数组中不断地向队尾方向移动，而在队首的前面产生一片不能利用的空闲存储区，最后会导致当尾指针指向数组最后一个位置（即r=m）而不能再加入元素时，存储空间的前部却有一片存储区无端浪费，这种现象称为“假溢出”。下图给出了一个“假溢出”的示例：克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就翻转为１。在结构上采用这种技巧来存储的队列称为循环队列，见图2循环队列循环队列队列必须构造成循环队列的形式,否则会出现“假溢出”constmaxsize=队列最大容量；m=maxsize-1;typecyclcquetp=recordelem:array[0..m]ofelemtp;r,f:0..m;end;初始时队列空，队首指针和队尾指针均指向存储空间的最后一个位置，即f=r=m。入队运算时，尾指针进一，即r←r+1；ifr=m+1thenr←1；这两条语句可用一条语句替代：r←rmodm+1；出队运算时，首指针进一，即f←f+1；iff=m+1thenf←1；这两条语句可用一条语句替代：f←fmodm+1；队列空时有f=r。队列满时有f=rmodm+1。（为了区分队列空和队列满，改用“队尾指针追上队首指针”这一特征作为队列满标志。这种处理方法的缺点是浪费队列空间的一个存储单元）循环队列的运算过程ADD2(q，x，r）{在循环队列q中插入一个新元素x}procedureADD2(varq：equeue；x：qtype；varr：integer)；begint←rmodm+1；{计算插入位置,即队尾}ift=fthenwriteln(‘full’){队列满}elsebegin{新元素x插入队尾}r←t；q[r]←x；end；{else}end；{ADD2}过程DEL2(q，y，f){从循环队列q中取出队首元素y}procedureDEL2(varq：equeue；vary：qtype；varf：inteqer)；beginiff=rthenwriteln(‘empty’){队列空}elsebeginf←fmodm+1；{计算删除位置，即队首}y←q[f]；{取出队首元素}end；{else}end；{DEL2}广度优先搜索从初始结点开始，应用算符生成第一层结点，检查目标结点是否在其中出现，若没有，再用算符将第一层结点逐一扩展，得第二层结点，逐一检查第二层中是否包含目标结点。若没有，依次扩展、检查……直到发现目标结点为止。这就是所谓的广度优先搜索。用队列的数据结构来存储搜索过程中产生的结点，取队头元素扩展，产生的结点插入队尾。abcdefjk算法框架在广度优先搜索中，我们将扩展出的状态存贮在一个称为list的数组里，数组容量为listmax。list数组采用“先进先出”的队列结构，设两个指针open、closed，分别是队尾指针和队首指针。其中list[1‥cloed-1]存贮已扩展状态（即这些状态的儿子状态已扩展出）；list[closed‥open]存贮待扩展状态（即这些状态的儿子状态尚待扩展）。当open=closed时，则表示队列空；当open=listmax时，则表示队列满(见上图)。List数组的元素为状态。typenode=状态的数据类型varlist：array[1．．listmax]ofnode；{队列}closed，open：integer；{队首指针和队尾指针}广度优先搜索的算法流程如下：open←1；closed←0；{初始状态进入队列}list[open]←初始状态；while(closedopen)and(open≤listmax)dobegin{若队列非空且未溢出，则移出队首状态，扩展其子状态}closed←closed+1；expand(list[closed])；{扩展队首状态的所有子状态}end；{while}ifopen≥listmax{若扩展出的状态数超出list表的容量上限}then输出内存溢出信息else找到了初始状态所能到达的所有状态list[1]．．list[open]；采用广度优先搜索的试题一般有两种类型：⑴求初始状态所能到达的所有状态⑵求初始状态到某目标状态的最短路径细胞一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。输入：整数m,n(m行，n列)（1=m=80,1=n=50）矩阵输出：细胞的个数。样例:输入:4100234500067103456050020456006710000000089输出:40234500067103456050020456006710000000089共4个细胞例3-1：（xibaoshumu.txt）一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。输入：整数m,n(m行，n列)（1=m=80,1=n=50）矩阵输出：细胞的个数。样例:输入:4100234500067103456050020456006710000000089输出:40234500067103456050020456006710000000089共4个细胞算法步骤：1、从文件中读入m*n矩阵，将其转换为0、1矩阵存入pic数组中；2、沿pic数组矩阵从上到下，从左到右，找到遇到的第一个细胞；将细胞的位置入队h，并沿其上、下、左、右四个方向上搜索，如果遇到细胞(pic[I,j]=1)则将其位置入队，入队后的位置pic[I,j]数组置为0；3、将h队的队头出队，沿其上、下、左、右四个方向上搜索，如果遇到细胞则将其位置入队，入队后的位置pic数组置为0；4、重复3，直至h队空为止，则此时找出了一个细胞；5、重复2，直至矩阵找不到细胞；6、输出找到的细胞数。constdx:array[1..4]of-1..1=(-1,0,1,0);dy:array[1..4]of-1..1=(0,1,0,-1);vars:string;pic:array[1..80,1..50]of0..1;{0:无细胞；1：有细胞}m,n,i,j,num:integer;h:array[1..4000,1..2]ofbyte;{队列：存细胞的坐标，1：行；2：列}proceduredoing(p,q:integer);{处理坐标（p,q）的细胞}vari,t,w,x,y:integer;begininc(num);{细胞数量加1}pic[p,q]:=0;t:=1;{队列头}w:=1;{队列尾}h[1,1]:=p;h[1,2]:=q;{遇到的第一个细胞入队}repeatfori:=1to4do{沿细胞的上下左右四个方向搜索细胞}beginx:=h[t,1]+dx[i];y:=h[t,2]+dy[i];if(x0)and(x=m)and(y0)and(y=n)and(pic[x,y]=1)thenbegininc(w);h[w,1]:=x;h[w,2]:=y;pic[x,y]:=0;end;{为细胞的入队}end;inc(t);{队头指针加1，出队列}untiltw;{直至队空为止}end;beginfillchar(pic,sizeof(pic),0);num:=0;fillchar(h,sizeof(h),0);assign(input,'a.in');reset(input);assign(output,'a.out');rewrite(output);readln(m,n);fori:=1tomdobeginreadln(s);forj:=1tondoifs[j]='0'thenpic[i,j]:=0elsepic[i,j]:=1;end;fori:=1tomdoforj:=1tondoifpic[i,j]=1thendoing(i,j);{在矩阵中寻找细胞}writeln(num);close(input);close(output);end.最少步数[问题描述]在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（19*19）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点的可能最少步数。[样例]输入：12161810输出：89题解由于A、B两点是随机输入的，因此无法找到计算最少步数的数学规律，只能通过广度优先搜索的办法求解。1、确定出发点从（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]）以及到达该点所需要的最少步数（queue[k,3]）（0≤k≤192+1）。队列的首指针为closed，尾指针为open。初始时，queue中只有一个元素为(1,1)，最少步数为0。S——记录(1,1)到每点所需要的最少步数。显然，问题的答案是s[x1,y2]和s[x2,y2]。初始时，s[1,1]为0，除此之外的所有元素值设为-1。为了使得马从棋盘内任意位置扩展出的坐标均在s的范围内，我们将s数组的范围扩大至s[-1..21,-1..21]。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）constdx：array[1..12]ofinteger=(-2,-2,-1,1,2,2,2,2,1,-1,-2,-2);dy：array[1..12