搜索算法个人总结pascal

2011．10．17总结（1-5题为今天重写一次，其下所表示的提交次数为今天重写的提交次数，其他题提交次数为原来的次数，部分不详，题号前加星号表示未AC）1·N皇后（位运算版）这个是看了标程后写的，很有意思很巧妙的做法，也很强大，一次wa，是因为没写inc（sum），。①（只输出结果数目）programquen;vark,sum,n:longint;proceduredfs(row,l,r:longint);//row：列l，r：两条对角线varpos,p:longint;beginifrowkthenbeginpos:=kandnot(lorrorrow);//表示需要放皇后的的位子whilepos0do//有皇后要放beginp:=posand(notpos+1);//取最右边的1//p表示某个可以放上皇后的地方pos:=pos-p;//放上皇后dfs(row+p,(l+p)shl1,(r+p)shr1);//回溯，注意对角线的处理end;endelseinc(sum);end;beginreadln(n);k:=(1shln)-1;//每一位都是1，目标状态dfs(0,0,0);writeln(sum);end.②（输出前3种方案，tyvj080）programquen{输出前3种解};vark,sum,n,i,t:longint;a:array[0..14]oflongint;proceduredfs(dep,row,l,r:longint);//dep：层数row：列l，r：两条对角线varpos,p,i:longint;beginifdepnthen//决策有效begininc(sum);ifsum=3thenbeginfori:=1tondowrite(a[i],'');//输出决策writeln;end;endelsebeginfori:=1tondo//第i位是否可以放皇后beginp:=(1shl(i-1));//二进制决策pos:=pand(roworlorr);//pos记录冲突if(pos=0)//没有冲突thenbegina[dep]:=i;//记录决策dfs(dep+1,row+p,(l+p)shl1,(r+p)shr1);//下一层递归end;end;endend;beginreadln(n);k:=(1shln)-1;//每一位都是1，目标状态fori:=1tondobegina[1]:=i;//初始化第一行，有n个状态t:=1shl(i-1);dfs(2,t,tshl1,tshr1);end;writeln(sum);end.2.计算细胞数一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:阵列0234500067103456050020456006710000000089有４个细胞输入格式InputFormat第一行：两个数字MN（1=Ｍ=501=N80）表示该阵列有Ｍ行Ｎ列从第２行到第Ｍ＋１行每行有连续的Ｎ个字符输出格式OutputFormat一行:细胞个数似乎我写出来的不是标准的搜索……//思路：以细胞中的一个点为起点，将他及他周围的不为0的点都改为0，然后找下一个。//提交情况：一次ACprogramtyvj1127;varn,m,re:longint;a:array[1..100,1..100]oflongint;procedureinit;beginassign(input,'tyvj1127.in');assign(output,'tyvj1127.out');reset(input);rewrite(output);end;procedurechange(i,j:longint);vark,l:longint;begina[i,j]:=0;ifi1thenifa[i-1,j]0thenchange(i-1,j);ifa[i+1,j]0thenchange(i+1,j);ifj1thenifa[i,j-1]0thenchange(i,j-1);ifa[i,j+1]0thenchange(i,j+1);end;procedureprepare;vari,j:longint;k:char;beginreadln(n,m);fori:=1tondobeginforj:=1tomdobeginread(k);val(k,a[i,j]);end;readln;end;re:=0;fori:=1tondoforj:=1tomdobeginifa[i,j]0thenbeginchange(i,j);re:=re+1;end;end;writeln(re);end;procedureoutit;beginclose(input);close(output);end;begininit；prepare;outit；end.3·滑雪trs喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-23…3-2-1更长，事实上这是最长的一条。输入文件第1行:两个数字r，c(1=r,c=100)，表示矩阵的行列。第2..r+1行:每行c个数，表示这个矩阵。输出文件仅一行:输出1个整数，表示可以滑行的最大长度。样例输入SampleInput5512345161718196152425207142322218131211109样例输出SampleOutput25记忆化搜索，也没设么好说的，就是刚开始的时候写出来总是无法跳出递归……提交情况：１次ＷＡ原因：没删ｉｎｐｕｔ和ｏｕｔｐｕｔprogramski;constmaxn=100;dx:array[1..4]oflongint=(0,-1,0,1);dy:array[1..4]oflongint=(1,0,-1,0);vara,f:array[1..maxn,1..maxn]oflongint;max,r,c,i,j:longint;functionbest(x,y:longint):longint;vari,x2,y2:longint;beginiff[x,y]0thenexit(f[x,y]);best:=1;fori:=1to4dobeginx2:=x+dx[i];y2:=y+dy[i];if(x2=r)and(x2=1)and(y2=c)and(y2=1)and(a[x,y]a[x2,y2])thenbeginifbest(x2,y2)+1bestthenbest:=best(x2,y2)+1;end;end;f[x,y]:=best;end;beginreadln(r,c);fori:=1tordoforj:=1tocdoread(a[i,j]);fillchar(f,sizeof(f),0);max:=0;fori:=1tordoforj:=1tocdobeginifbest(i,j)maxthenmax:=best(i,j);end;writeln(max);end.**4·Sramoc问题(SramocProblem)问题描述：Sramoc(K,M)表示用数字0、1、２…、K-1组成的自然数中能被M整除的最小数。给定K、M，求Sramoc(K,M)。例如K=2，M=7的时候，Sramoc(2,7)=1001。输入格式：从文件SRAMOC.DAT读入数据。第一行为两个整数K、M满足2=K=10、1=M=1000。输出格式：输出Sramoc(K,M)到SRAMOC.OUT。样例SRAMOC.DATSRAMOC.OUT271001思路：广搜，从1位数的余数出发，不停扩展，生成新余数，直到余数0第一次出现提交情况：一次９０分原因直接扩展有一组的答案超出了ｑｗｏｒｄ的最大值……改进思路，每次只记录一位。90分程序如下：programsramoc;vark,m:longint;d:array[0..100000]ofqword;hash:array[0..2000]oflongint;procedureinit;beginassign(input,'sramoc.in');assign(output,'sramoc.out');reset(input);rewrite(output);end;procedureprepare;vari,j:longint;beginreadln(k,m);end;procedureoutit;源程序名sramoc.???（pas,c,cpp）可执行文件名sramoc.exe输入文件名sramoc.in输出文件名sramoc.outbeginclose(input);close(output);halt;end;proceduremain;varl,r,i,j:longint;x,y:qword;beginl:=0;r:=0;fillchar(hash,sizeof(hash),0);fori:=1tok-1dobegind[i]:=i;ifd[i]modm=0thenbeginwriteln(d[i]);outit;end;r:=r+1;hash[d[i]modm]:=1;end;repeatl:=l+1;x:=d[l];fori:=0tok-1dobeginy:=x*10+i;ifymodm=0thenbeginwriteln(y);outit;end;ifhash[ymodm]=0thenbeginr:=r+1;d[r]:=y;hash[ymodm]:=1;end;end;untill=r;end;begininit;prepare;main;outit;end.**5·黑白棋游戏源程序名game.???（pas,c,cpp）可执行文件名game.exe输入文件名game.in输出文件名game.out【问题描述】黑白棋游戏的棋盘由4×4方格阵列构成。棋盘的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。这16枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有1条公共边的2个方格称为相邻方格。一个方格最多可有4个相邻方格。在玩黑白棋游戏时，每一步可将任何2个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。【输入】输入文件共有8行。前四行是初始游戏状态，后四行是目标游戏状态。每行4个数分别表示该行放置的棋子颜色。“0”表示白棋；“1”表示黑棋。【输出】输出文件的第一行是着棋步数n。接下来n行，每行4个数分别表示该步交换棋子的两个相邻方格的位置。例如，abcd表示将棋盘上(a，b)处的棋子与(c，d)处的棋子换位。【样例】game.ingame.out1111400001222111014240010324210104344010110100101广搜，用位运算记录及更改状态，分别处理上下交换和左右交换.提交情况:4次——60分前3次提交分别是输出格式不对，第4,8,12位没有单独处理60分的程序如下（4组方案不对）：programgame;typemm=recordnum,st,c1,c2,cn:longint;end;constp:array[1..16,1..2]oflongint=((4,4),(4,3),(4,2),(4,1),(3,4),(3,3),(3,2),(3,1),(2,4),(2,3),(2,2),(2,1),(1,4),(1,3),(1,2),(1,1));varss,tt:array[0..4,0..4]oflongint;d:array[0..1000000]ofmm;s,t:longint;procedureinit;beginassign(input,'game.i