jsoi2012夏令营层次第四讲

Jsoi2012夏令营B——BFSBFS所遵循的搜索策略是按层次搜索。r=max

By.BFS=O(c^k)orO(c^d)C为分支数，dvoidvoidbfs(int{foricurtocur{ifv｛if(v==n)}until} dx:Array[1..4]dy:Array[1..4]ofTypenode=Recordx,y:integer;p:integer;q:array[1..100]Integer=(1,0,-1,Integer=(0,1,0,-g:array[0..11,0..11]of cur:node;n,f,r,x,y,i:integer;ProcedureBFS;f:=1;r:=2;q[1].x:=1;q[1].y:=1;q[1].p:=0;g[1,1]:=cur:=Fori:=1to4Dox:=cur.x+dx[i];y:=cur.y+Ifg[x,y]= Thenq[r].x:=x;q[r].y:=y;q[r].p:=f;Inc(r);g[x,y]:=1;If(x=n)and(y=n)ThenPrint(r-1);Until(f=ProcedurePrint(n:i,j:s:array[1..100]ofi:=Whileq[n].p<>0DoInc(i);s[i]:=q[n];n:=Forj:=iDownto1DoWrite('->(',s[j].x,',',s[j].y,')'); EX1.10L10L3L7L的空容器各一个，现在请你10L5L。六种倒油方式（107，103，710，73，310，37）判重：顺序查找队列用一个三维（或二维）行以及该倒多少油（10L7L为例）(C10>0)And(C7C10+C7>7C10+C7EX2.倒水问题（上机练习有两个没有刻度的，其容量是V1和V2，另有一无限容量的水缸，里面有无限多水我们可以用水缸中的水将装满也可以将中的水全部倒入水缸，或者将水从一个倒入另一个中（必须倒光或者另一个满为止，现请你找出一个方案，使得1或2或1+2中的水正好等于V3V1、V2V3V1和V22^7，V3（此题可能无解35EX3.在一个n×nm位骑士，每年他们都要聚会一次，所有的骑士都nm2m+12xy512243EX4.A$，B$及一组字串变换的规则(6个规则A$中的子串A1$可以变换为B1$A2$可以变换为B2$……。例如：A$='abcd'B$='xyz''abc'→'xu''ud'→'y'则此时，A$B$，其变换的过程为：A$n规则数目，以下为n条规则}A1$B1$A2$20出"NOANSWER"abcdxyzabcxuudyy3(1/a的a是自然数)表示一切有理数。如：2/3=1/2+1/6,2/3=1/3+1/3,因为加数中有相同的。对于一个分数a/b,表示方法有很多种，但是哪种最好呢？首先，加数少的比19/45=1/3+1/12+19/45=1/3+1/15+19/45=1/3+1/18+19/45=1/4+1/6+19/45=1/5+1/6+1/181/180,1/45,1/30,1/180都大。给出一行用一个空格隔开的两个整数a和b一行用一个空格隔开的两个整数a和bproceduredfs(k,q:longint;x,y:qword);vari:longint;proceduredfs(k,q:longint;x,y:qword);vari:longint; x:=xdivw;y:=ydivw;ifk=t-1thenif(x=1)and(Y>c[k])the