搜索算法个人总结pascal.doc

20111017总结 （1-5题为今天重写一次，其下所表示的提交次数为今天重写的提交次数，其他题提交次数为原来的次数，部分不详，题号前加星号表示未AC）1N皇后（位运算版）这个是看了标程后写的，很有意思很巧妙的做法，也很强大，一次wa，是因为没写inc（sum），。（只输出结果数目）program quen;var k,sum,n:longint;procedure dfs(row,l,r:longint); /row：列 l，r：两条对角线var pos,p:longint;begin if rowk then begin pos:=k and not(l or r or row); /表示需要放皇后的的位子 while pos0 do /有皇后要放 begin p:=pos and(not pos +1); /取最右边的1 /p表示某个可以放上皇后的地方 pos:=pos-p; /放上皇后 dfs(row+p,(l+p)shl 1,(r+p)shr 1 ); /回溯，注意对角线的处理 end ; end else inc(sum);end;begin readln(n); k:=(1 shl n)-1; /每一位都是1，目标状态 dfs(0,0,0); writeln(sum);end. （输出前3种方案，tyvj080） program quen输出前3种解;var k,sum,n,i,t:longint; a:array0.14of longint;procedure dfs(dep,row,l,r:longint); /dep： 层数 row：列 l，r：两条对角线var pos,p,i:longint;begin if depn then /决策有效 begin inc(sum); if sum=3 then begin for i:=1 to n do write(ai, ); /输出决策 writeln; end; end else begin for i:=1 to n do /第i位是否可以放皇后 begin p:=(1 shl (i-1); /二进制决策 pos:=p and (row or l or r); /pos记录冲突 if(pos=0) /没有冲突 then begin adep:=i; /记录决策 dfs(dep+1,row + p,(l+p)shl 1,(r+p)shr 1); /下一层递归 end; end; endend;begin readln(n); k:=(1 shl n)-1; /每一位都是1，目标状态 for i:=1 to n do begin a1:=i; /初始化第一行，有n个状态 t:=1 shl(i-1); dfs(2,t,t shl 1,t shr 1); end; writeln(sum);end.2. 计算细胞数一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。 如:阵列 0234500067 1034560500 2045600671 0000000089 有个细胞输入格式 Input Format第一行：两个数字M N （1=50 1=N1 then if ai-1,j0 then change(i-1,j); if ai+1,j0 then change(i+1,j); if j1 then if ai,j-10 then change(i,j-1); if ai,j+10 then change(i,j+1);end;procedure prepare;var i,j:longint; k:char;begin readln(n,m); for i:=1 to n do begin for j:=1 to m do begin read(k); val(k,ai,j); end; readln; end; re:=0; for i:=1 to n do for j:=1 to m do begin if ai,j0 then begin change(i,j); re:=re+1; end; end; writeln(re);end;procedure outit;begin close(input) ; close(output);end;begin init； prepare; outit；end.3滑雪trs喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-233-2-1更长，事实上这是最长的一条。输入文件第1行: 两个数字r，c(1=r,c0 then exit(fx,y);best:=1;for i:=1 to 4 do begin x2:=x+dxi; y2:=y+dyi; if (x2=1)and(y2=1)and(ax,yax2,y2) then begin if best(x2,y2)+1best then best:=best(x2,y2)+1; end; end;fx,y :=best;end;begin readln(r,c); for i:=1 to r do for j:=1 to c do read(ai,j); fillchar(f,sizeof(f),0); max:=0; for i:=1 to r do for j:=1 to c do begin if best(i,j)max then max:=best(i,j); end; writeln(max); end.*4Sramoc问题 ( Sramoc Problem )源程序名 sramoc.?（pas, c, cpp）可执行文件名 sramoc .exe输入文件名 sramoc .in输出文件名 sramoc .out问题描述：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.OUT2 71001思路：广搜，从1位数的余数出发，不停扩展，生成新余数，直到余数0第一次出现提交情况：一次分原因直接扩展有一组的答案超出了的最大值改进思路，每次只记录一位。90分程序如下：program sramoc;var k,m:longint; d:array0.100000of qword; hash:array0.2000of longint;procedure init ;begin assign(input,sramoc.in); assign(output,sramoc.out); reset(input); rewrite(output);end;procedure prepare;var i,j:longint;begin readln(k,m);end;procedure outit;begin close(input) ; close(output); halt;end;procedure main;var l,r,i,j:longint; x,y:qword;begin l:=0;r:=0; fillchar(hash,sizeof(hash),0); for i:=1 to k-1 do begin di:=i; if di mod m=0 then begin writeln(di); outit; end; r:=r+1; hashdi mod m:=1; end;repeat l:=l+1; x:=dl; for i:=0 to k-1 do begin y:=x*10+i; if y mod m=0 then begin writeln(y); outit; end; if hashy mod m=0 then begin r:=r+1;dr:=y; hashy mod m:=1; end; end; until l=r;end;begin init; prepare; main; outit;end. *5黑白棋游戏源程序名 game.?（pas, c, cpp）可执行文件名 game.exe输入文件名 game.in输出文件名 game.out【问题描述】黑白棋游戏的棋盘由44方格阵列构成。棋盘的每一方格中放有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组方案不对）：program game;type mm=record num,st,c1,c2,cn:longint; end;const p:array1.16,1.2of longint=(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);var ss,tt:array0.4,0.4of longint; d:array0.1000000of mm; s,t:longint;procedure init ;begin assign(input,game.in); assign(output,game.out); reset(input); rewrite(output);end;procedure prepare;var i,j,k,w:longint; s1,c:string;begin s:=0; t:=0; for i:=1 to 4 do begin readln(s1); for j:=1 to 4 do begin c:=s1j; val(c,ssi,j); k:=17-(i-1)*4+j); s:=s+(ssi,jshl (k-1); end; end; for i:=1 to 4 do begin readln(s1); for j:=1 to 4 do begin c:=s1j; val(c,tti,j); k:=17-(i-1)*4+j); t:=t+(tti,jshl (k-1); end; end;end;procedure outit;begin close(input) ; close(output); halt;end;procedure print(x:longint);var i,last,j,k:longint;begin if x=1 then exit; last:=dx.st; j:=dx.c2; k:=dx.c1; write(pj,1,pj,2); writeln(pk,1,pk,2); print(last);end;procedure main;var i,j,l,r,x,y:longint; hash:array0.100000of boolean;begin fillchar(hash,sizeof(hash),false); hashs:=true; d1.num:=s; :=0; l:=0; r:=1; repeat l:=l+1; x:=dl.num; for i:=1 to 15 do begin if (x shr (i-1)and 1)(x shr(i)and 1)and(i4)and(i8)and(i12) then begin y:=x xor(1 shl(i-1); y:=y xor(1 shl(i); if hashy=false then begin r:=r+1; dr.num:=y; dr.st:=l; dr.c1:=i; dr.c2:=i+1; :=+1; hashy:=true; end; if y=t then begin writeln(); print(r); outit; end; end; if (i=12)and(x shr (i-1)and 1)(x shr(i+4-1)and 1) ) then begin y:=x xor(1 shl(i-1); y:=y xor(1 shl(i+3); if hashy=false then begin r:=r+1; dr.num:=y; dr.st:=l; dr.c1:=i; dr.c2:=i+4; :=+1; hashy:=true; end; if y=t then begin writeln();print(r); outit; end; end; end; until l=r;end;begin init; prepare; main; outit;end.6迷宫(maze.pas/c/cpp)【问题描述】电脑游戏中有许多令人头疼的迷宫，会花费玩家相当多的时间，你通过秘笈获得了游戏迷宫的地图，你希望找到最短的一条走出迷宫的道路，并且想知道一共有多少条最短的道路，但是由于地图非常庞大，所以你不能在短时间找出这些道路，因此，你需要编写一个程序来找出这些最短的道路，并且统计一下一共有多少条这样的道路。例如，对于下图所示的迷宫：SXXXXEX表示障碍物，不可以通过，S表示迷宫的入口，E表示迷宫的出口。显然，从入口到出口至少需要走6步，而长度为6的道路一共有两条。输入文件maze.in，第一行是一个整数n（1 n 25），表示迷宫是一个nn的矩阵。以下n行每行有n个字符来描述地图，“.”表示可以通过，“X”表示不可以通过，“S”表示迷宫的入口，“E”表示迷宫的出口。（注意：所有的字母均为大写）。输出文件maze.out包括两行，第一行包含一个整数，表示从入口到出口走的最短距离。第二行包含一个整数，表示最短路径的调数，答案保证小于231。【样例输入】4S.XX.XX.E.【样例输出】62 写两个广搜先找距离再找条数（此程序用动规的思想，写的类似广搜）提交情况：一次acprogram maze;var map:array0.50,0.50of char; a,b:array0.850,0.50of longint; n,sx,sy,ex,ey:longint;procedure init ;begin assign(input,maze.in); assign(output,maze.out); reset(input); rewrite(output);end;procedure prepare;var i,j:longint;begin readln(n); for i:=1 to n do begin for j:=1 to n do begin read(mapi,j); if mapi,j=S then begin sx:=i; sy:=j; end; if mapi,j=E then begin ex:=i; ey:=j; end; end; readln; end;end;procedure outit;begin close(input) ; close(output);end;procedure chang;var i,j,f,t:longint; dui:array1.2000,1.2of longint;begin for i:=1 to n do for j:=1 to n do ai,j:=-1; f:=0; t:=1; asx,sy:=0; dui1,1:=sx; dui1,2:=sy; repeat f:=f+1; i:=duif,1; j:=duif,2; if (ai-1,j0)and(mapi-1,jX) then begin t:=t+1; ai-1,j:=ai,j+1; duit,1:=i-1; duit,2:=j; end; if (ai+1,j0)and(mapi+1,jX) then begin t:=t+1; ai+1,j:=ai,j+1; duit,1:=i+1; duit,2:=j; end; if (ai,j-10)and(mapi,j-1X) then begin t:=t+1; ai,j-1:=ai,j+1; duit,1:=i; duit,2:=j-1; end; if (ai,j+10)and(mapi,j+1X) then begin t:=t+1; ai,j+1:=ai,j+1; duit,1:=i; duit,2:=j+1; end; if aex,ey0 then exit; until f=t;end;procedure lujin;var i,j,f,t:longint; dui:array1.2000,1.2of longint; k:array0.50,0.50of boolean;begin fillchar(b,sizeof(b),false); fillchar(dui,sizeof(dui),0); fillchar(k,sizeof(k),0); f:=0; t:=1; bsx,sy:=1; dui1,1:=sx; dui1,2:=sy; ksx,sy:=true; repeat f:=f+1; i:=duif,1; j:=duif,2; if (ai-1,j=ai,j+1)and(bi,j0) then begin bi-1,j:=bi-1,j+bi,j; if not(ki-1,j) then begin t:=t+1; duit,1:=i-1; duit,2:=j; ki-1,j:=true; end; end; if (ai+1,j=ai,j+1)and(bi,j0) then begin bi+1,j:=bi+1,j+bi,j; if not(ki+1,j) then begin t:=t+1; duit,1:=i+1; duit,2:=j; ki+1,j:=true; end; end; if (ai,j-1=ai,j+1)and(bi,j0) then begin bi,j-1:=bi,j-1+bi,j; if not(ki,j-1) then begin t:=t+1; duit,1:=i; duit,2:=j-1; ki,j-1:=true; end; end; if (ai,j+1=ai,j+1)and(bi,j0) then begin bi,j+1:=bi,j+1+bi,j; if not(ki,j+1) then begin t:=t+1; duit,1:=i; duit,2:=j+1; ki,j+1:=true; end; end; until f=t;end;procedure main;var i,j:longint;begin chang; if aex,ey0 then begin writeln(aex,ey); lujin; write(bex,ey); end else begin writeln(0); write(0); end;end;begin init; prepare; main; outit;end.7靶形数独(sudoku.pas/c/cpp)【问题描述】小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z博士请教，Z 博士拿出了他最近发明的“靶形数独” ，作为这两个孩子比试的题目。 靶形数独的方格同普通数独一样，在 9 格宽9 格高的大九宫格中有 9 个 3 格宽3 格高的小九宫格（用粗黑色线隔开的） 。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 1到 9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红色区域）每个格子为 9 分，再外面一圈（蓝色区域）每个格子为 8分，蓝色区域外面一圈（棕色区域）每个格子为 7分，最外面一圈（白色区域）每个格子为 6 分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法） ，而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 2829。游戏规定，将以总分数的高低决出胜负。由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。【输入】输入文件名为 sudoku.in。一共 9 行。每行 9 个整数（每个数都在 09 的范围内） ，表示一个尚未填满的数独方格，未填的空格用“0”表示。每两个数字之间用一个空格隔开。【输出】输出文件 sudoku.out共 1行。输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。【输入输出样例 1】sudoku.in sudoku.out7 0 0 9 0 0 0 0 1 28291 0 0 0 0 5 9 0 00 0 0 2 0 0 0 8 00 0 5 0 2 0 0 0 30 0 0 0 0 0 6 4 84 1 3 0 0 0 0 0 00 0 7 0 0 2 0 9 02 0 1 0 6 0 8 0 40 8 0 5 0 4 0 1 2【输入输出样例 2】sudoku.insudoku.out0 0 0 7 0 2 4 5 3 28529 0 0 0 0 8 0 0 07 4 0 0 0 5 0 1 01 9 5 0 8 0 0 0 00 7 0 0 0 0 0 2 50 3 0 5 7 9 1 0 80 0 0 6 0 1 0 0 00 6 0 9 0 0 0 0 10 0 0 0 0 0 0 0 6【数据范围】40%的数据，数独中非 0数的个数不少于 30。80%的数据，数独中非 0数的个数不少于 26。100%的数据，数独中非 0 数的个数不少于 24。这道题不用说肯定是搜索，和八皇后相似，但状态比较难以保存和判断，我是把每一行每一列每一个小格映射成一个二进制数，从右数第n位表示n是否用过。其中用到一些位运算，比如说把右数第k位变成1：x or (1 shl (k-1)把右数第k位变成0： x and not (1 shl (k-1）取右数第k位：x shr (k-1) and 1搜索当然时间效率很低，顺搜过55%左右，倒搜只有一组过不到，于是加一个卡时。调试了很久，最开始搜索部分判断是否用过写的有点问题，导致就是没结果，后来计算权值和的过程中出现超界，静态检查时没发现于是一通狂调然后过了一会猛然发现dfs的时候绝对不会出现超界的情况，然后一看计算部分就发现了错误！另提交次数：不详（太多次，实在记不到了）代码：program sudoku;const ying:array1.9,1.9of longint=(1,1,1,2,2,2,3,3,3), 每一个格子对应小方格的编号 (1,1,1,2,2,2,3,3,3), (1,1,1,2,2,2,3,3,3), (4,4,4,5,5,5,6,6,6), (4,4,4,5,5,5,6,6,6), (4,4,4,5,5,5,6,6,6), (7,7,7,8,8,8,9,9,9), (7,7,7,8,8,8,9,9,9), (7,7,7,8,8,8,9,9,9) ; v:array1.9,1.9of longint=(6,6,6,6,6,6,6,6,6),每一个格子的分值 (6,7,7,7,7,7,7,7,6), (6,7,8,8,8,8,8,7,6), (6,7,8,9,9,9,8,7,6), (6,7,8,9,10,9,8,7,6), (6,7,8,9,9,9,8,7,6), (6,7,8,8,8,8,8,7,6), (6,7,7,7,7,7,7,7,6), (6,6,6,6,6,6,6,6,6) ;var x,y,xiao:array1.9of longint;x，y，xiao：分别为每一个横排，竖列，小方格的状态 a:array1.9,1.9of longint; d:array1.81,1.2of longint; re,t,ka:longint;procedure init ;begin assign(input,sudoku.in); assign(output,sudoku.out); reset(input); rewrite(output);end;procedure outit;begin close(input) ; close(output); halt;end;function pan(i,j,k:longint):boolean;var er:longint;begin er:=xi or yj or xiaoyingi,j; er：横、竖、小方格的所有条件加到一起 er:=ershr(k-1); er转成二进制后的第k位，即在当前行、列、和小方格中k有无用过 if er and 1=1 then exit(false); exit(true);end;procedure jishuan;var i,j,sum:longint;begin sum:=0; for i:=1 to 9 do for j:=1 to 9 do begin sum:=sum+ai,j*vi,j; end; ka:=ka+81; if sumre then re:=sum;end;procedure dfs(dep:longint);var i,j,k:longint; s:string;begin i:=ddep,1; j:=ddep,2; if ka100000000 then begin writeln(re); outit; end; 如果将要超时就直接输出当前最大值 for k:=1 to 9 do begin inc(ka); if pan(i,j,k) 判断（i，j）这个位置可不可以放数k then begin xi:=xi