搜索算法个人总结pascal.doc

(1-5题为今天重写一次,其下所表示的提交次数为今天重写的提交次数,其他题提交次数为原来的次数,部分不详,题号前加星号表示未AC)1〃N皇后(位运算版)这个是看了标程后写的,很有意思很巧妙的做法,也很强大,一次wa,是因为没写inc(sum),。①(只输出结果数目)programquen;vark,sum,n:longint;proceduredfs(row,l,r:longint);//row:列l,r:两条对角线varpos,p:longint;beginifrow<>kthenbeginpos:=kandnot(lorrorrow);//表示需要放皇后的的位子whilepos<>0do//有皇后要放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;beginifdep>nthen//决策有效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);,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:阵列02345000671034560500204560067**********有4个细胞输入格式InputFormat第一行:两个数字MN(1<=M<=501<=N<80)表示该阵列有M行N列从第2行到第M+1行每行有连续的N个字符输出格式OutputFormat一行:细胞个数似乎我写出来的不是标准的搜索……//思路:以细胞中的一个点为起点,将他及他周围的不为0的点都改为0,然后找下一个。//提交情况:一次ACprogramtyvj1127;varn,m,re:longint;a:array[1..100,1..100]oflongint;procedureinit;beginassign(input,'');assign(output,'');reset(input);rewrite(output);end;procedurechange(i,j:longint);vark,l:longint;begina[i,j]:=0;ifi>1thenifa[i-1,j]>0thenchange(i-1,j);ifa[i+1,j]>0thenchange(i+1,j);ifj>1thenifa[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);end;writeln(re);end;procedureoutit;begi