nbhkdz.com冰点文库

深度优先搜索


栈与递归

?
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

例0-1:输入一个正整数n,求n的阶乘
var n : integer; function fac(n:integer):longint; begin if n = 0 then fac := 1 else fac := n

* fac(n-1); end; begin readln(n); writeln(fac(n)); end.

?

要理解递归,首先应了解一种数据结构:堆 栈(简称栈)的概念。

?

栈(stack)又名堆栈,它是一种运算受限的线性表。 其限制是仅允许在表的一端进行插入和删除运算。这一 端称为栈顶,相对地,把另一端称为栈底。向一个栈插 入新元素称作进栈、入栈或压栈;从一个栈删除元素又 称作出栈或退栈。

3

2

1

Init初始化栈 Procedure init; Begin top := 0; End;

栈指针top

3

2

1

Push入栈

Procedure push(x:integer);
Begin top := top + 1; if isfull = false then Stack[top] := x;

else
栈指针top End; writeln(‘stack full’);

3

2

1 栈指针top

Isfull判栈满 Function isfull; n+1 Begin if top = n + 1 then; isfull := true; else isfull := false;

End;

Gettop取栈顶元素
Function gettop:integer Begin gettop : = stack[top]; End;

栈指针top 3
2 1

Push出栈
Procedure pop; Begin if isempty = true then write(‘stack empty’)

栈指针top 3
2 1

else
top : = top – 1; End;

栈空

3

2

1

Isempty判栈空 Function isempty; Begin if top = 0 then; isempty := true; else isempty := false;

栈指针top

End;
0

?

例0-2:输入n个整数,并逆序输出(栈实现)。

输入样例: 3 123 输出样例: 321

1. 2. 3. 4. 5.
6. 7. 8. 9.

const maxn = 20; var stack : array[1..maxn] of integer; top : integer; n, i, x : integer;
procedure init; begin top := 0; end;

10. function isfull:boolean; 11. begin 12. if top = n + 1 then 13. isfull := true 14. else 15. isfull := false; 16. end;

1. 2. 3. 4. 5. 6. 7.

function isempty:boolean; begin if top = 0 then isempty := true else isempty := false; end;

8. procedure push(x:integer); 9. begin 10. top := top + 1; 11. if isfull = true then 12. writeln('Stack Full') 13. else 14. stack[top] := x; 15. end;

1. function gettop:integer; 2. begin 3. gettop := stack[top]; 4. end; 5. procedure pop; 6. begin 7. if isempty = true then 8. writeln('Stack Empty') 9. else 10. top := top - 1; 11. end;

1. begin 2. readln(n); 3. for i := 1 to n do 4. begin 5. read(x); 6. push(x); 7. end; 8. while isempty <> true do 9. begin 10. write(gettop,' '); 11. pop; 12. end; 13. end.

?

编译器处理函数调用时,就是使用栈来保存数据的。当主调函 数调用另一个函数时,编译器将主调函数的所有实参和返回地 址压入到栈中,栈指针将移到合适的位置来容纳这些数据。

Function 函数1:integer; Begin 函数2; End;

函数1调用函数2系统栈中的变化(入栈)

?

当进行被调函数时,编译器将栈中的实参数据弹出,赋值给函 数的形参。在被调用函数执行期间,还可利用栈来保存函数执 行时的局部变量。当被调用函数准备返回时,系统将弹出栈中 所有当前函数压入栈中的值,这时,栈指针移动到被调用函数 刚开始执行时的位置。接着被调用函数返回,系统从栈中弹出 返回地址,主调函数就可以继续执行了。

函数2返回至函数1系统栈中的变化(出栈)

?
?

回到阶乘的递归算法上来。假设要计算5的阶乘,通过前面设 计的递归程序执行过程如下。 首先,在主函数中调用fact(5)函数,将返回地址、参数、局部
变量压入堆栈。

?

在fact()函数中,判断n的值若不为0,则递归调用 fact(4),这时将函数的返回地址和参数压入堆栈。

?

程序继续递归调用时,将fact(3)、fact(2)、fact(1) 逐步压入堆栈

?

当调用fact(0)时,达到阶乘递归算法的结束条件, 这时结束fact(0)函数调用,从堆栈中弹出该层的相 关数据,并返回函数的结果1。这时栈顶中保存的将 是fact(1)中的相关数据

?

当递归函数逐层返回时,栈中压入的数据将逐步弹 出,当弹出fact(4)后的栈结果如图所示

?

当函数fact(5)返回时得到5的阶乘等于120,同时从 栈中弹出调用函数时的数据,完成整个递归调用, 并返回主函数输出执行。

搜索
深度优先搜索

一、算法模型 二、经典应用

一、引例
? 例1:输入一个数n,按字典序从小到大的顺序 输出1~n的全排列。两个序列的字典序大小关 系等价于从开始的第一个不相同位置处的大小 关系。例如,(1,3,2) < (2,1,3) ? 当n = 3时,所有排序的排序结果是(1,2,3)、 (1,3,2)、(2,1,3)、(2,3,1)、(3,1,2) 、(3,2,1)。

一、引例
? 方法一 1. var a, b, c : integer; 2. begin 3. for a := 1 to 3 do 4. for b := 1 to 3 do 5. for c := 1 to 3 do 6. begin 7. if (a <> b) and (b <> c) and (c <> a) then 8. writeln(a,' ',b,' ',c); 9. end; 10.end.

? 方法一、穷举法 ? 寻找问题解的一种可靠的方法是首先列出 所有可能候选解,然后依次检查每一个,在检 查完所有或部分候选解后,即可找到所需要的 解。理论上,当候选解数量有限并且通过检查 所有或部分候选解能够得到所需解时,上述方 法是可行的。不过在实际应用中,很少使用这 种方法,因为候选解的数量通常都非常大,即 便采用最快的计算机也只能解决规模很小的问 题。

? 方法二 ? 这里我们先将这个问题形象化,举个例子, 假设有编号为1、2、3的3张扑克牌和编号为1、 2、3的3个盒子。现在需要将这3张扑克牌分别 放到3个盒子里面,并且每个盒子有且只能放一 张扑克牌,那么一共有多少种不同的方法呢?

一、引例
? 方法二、回溯法 ? 从问题的某一种可能出发, 搜索从这种情况 出发所能达到的所有可能, 当这一条路走到“ 尽头 ”而没达到目的地的时候, 再倒回上一个 出发点, 从另一个可能出发, 继续搜索. 这种不断 “ 倒回 一步"寻找解的方法, 称作" 回溯法 ".

? ?

程序实现 我们先来解决最基本的问题:如何往小盒子中放扑克 牌。每一个小盒子都可能放1号、2号或者3号扑克牌 ,这需要一一尝试,用一个for循环即可解决。 1. for i := 1 to n do //枚举1~n张牌 2. a[step] := i; //将i号扑克牌放入到第step个盒子中 ? 分析:数组a用来表示小盒子,变量step表示当前正处 在第step个小盒子面前。a[step] := i; 表示将i号扑克牌 放入到第step个盒子中。

?

1. 2. 3. 4. 5. 6. 7. 8.

这里有一个问题:如果判断该扑克牌是否还在手中,而没 有放入其他盒子中? for i = 1 to n do begin If used[i] = false then //如果i号扑克牌仍在手中 begin a[step] := i; //将i号扑克牌放入到第step个盒子中 used[i] := true; //标记i号扑克牌已不在手中 end; end; 1 2 3 1 2 3 1 2 3

F

F

F

T

F

F

T

T

F

?

OK,现在已经处理完第step个小盒子了,接下来需要往下走一步, 继续处理第step+1盒小盒子,处理方法与第step步完全相同。因此我 们不妨将刚才处理第step个小盒子的代码封装为一个函数,函数的名 字就叫做dfs吧!

1. procedure dfs(step:integer) 2. begin 3. for i := 1 to n do 4. begin 5. If used[i] = false 6. begin 7. a[step] := i; 8. used[i] := true; 9. end; 10. end; 11. end;

?

由此,处理第step个盒子,我们可调用dfs(step)完成,而处理第 step+1个盒子,就是dfs(step+1)……由此我们不妨使用函数的递归 调用加以实现。

1. procedure dfs(step:integer) 2. begin 3. for i := 1 to n do 4. begin 5. if used[i] = false begin 6. a[step] := i; 7. used[i] := true; 8. dfs(step+1); //继续尝试第step+1个盒子 9. used[i] = false; //取回刚刚尝试的那张牌 10. end; 11. end; 12. end;

?

再次提醒:如果在回溯法中使用了辅助的全局 变量,一定要及时把它们恢复原状!!!特别 地,若函数有多个出口,则需在每个出口处恢 复被修改的值。
1 2 3 1 2 3

T

T

F
递归调用

T

T

T

dfs(step)

dfs(step+1)

?

再次提醒:如果在回溯法中使用了辅助的全局 变量,一定要及时把它们恢复原状!!!特别 地,若函数有多个出口,则需在每个出口处恢 复被修改的值。
1 2 3 1 2 3

T

T

F

T

T

T

dfs(step)

dfs(step+1)

回溯

?

还剩下最后一个问题:就是什么时候输出一个满足要求的序列呢 ?其实当我们处理到第n+1个小盒子的时候(即step等于n+1), 说明前n个盒子都已经放好扑克牌了,这时将1~n个小盒子中的扑 克牌编号打印出来即可。

1. 2. 3. 4. 5. 6. 7. 8.

procedure dfs(step:integer) begin if step = n+1 then print; else for i := 1 to n do …… end;

step = n + 1

1. const maxn = 20; 2. var a : array[1..maxn] of integer; 3. used : array[1..maxn] of boolean; 4. n : integer; 5. 6. 7. 8. 9. 10. 11. procedure print; var i : integer; begin for i := 1 to n do write(a[i],' '); writeln; end;

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

procedure dfs(step:integer); var i : integer; begin if step = n + 1 then print else for i := 1 to n do begin if used[i] = false then begin a[step] := i; used[i] := true; dfs(step+1); used[i] := false; end; end; end;

1. begin 2. fillchar(used,sizeof(used),false); 3. readln(n); 4. dfs(1); 5. end.

?
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.

算法框架
procedure dfs(step:integer) begin if 到达边界状态 then 输出解; else for i := 1 to n do //顺次尝试每一种可能 begin if 满足条件 then begin 保存结果; dfs(step+1); 恢复:保存结果之前的状态 end; end; end; Begin dfs(1); end.

? ? ?

?

深度优先搜索(Depth First Search,DFS) 主要思想:不撞南墙不回头 深度优先遍历的主要思想就是:首先以一个未被访 问过的顶点作为起始顶点,沿当前顶点的边走到未 访问过的顶点;当没有未访问过的顶点时,则回到 上一个顶点,继续试探访问别的顶点,直到所有的 顶点都被访问。 沿着某条路径遍历直到末端,然后回溯,再沿着另 一条进行同样的遍历,直到所有的顶点都被访问过 为止。

分析:通过图例可以非常直观的了解 深度优先搜索的工作方式。下面来分 析一下如何用代码来实现它。
大家都知道,深度优先的主要思想就 是“不撞南墙不回头”,“一条路走 到黑”,如果遇到“墙”或者“无路 可走”时再去走下一条路。 所以先规定好一个走路的规则,比如 就按照右下左上顺时针的方式去尝试。

如上图僵尸的位置是起始点,先往右 走,但是有堵墙走不了,所以按照规 定尝试往下走。到达“1”的位置,此 时重复刚才的步骤,先向右走可以走 到“2”,再重复规则发现向右可以走 到“3”,再重复发现“下右左上”四 个方向都不能走,这时候就退回“2” 的位置尝试向下走。。。依次类推直 到走到最终的目的地。

二、经典问题
? ? 例2:八皇后问题 描述:在棋盘上放置8个皇后,使得它们互不 攻击,此时每个皇后的攻击范围为同行同列和 同对角线,要求找出所有解。

二、经典问题
? ? 例2:八皇后问题 不难发现以下事实:恰好每行每列各放置一个 皇后。如果用 C[x] 表示第 x 行皇后的列编号, 则问题变成了全排列生成问题。而1~8的排列 一共只有8! = 40320个,枚举量不会超过它。
C[1] := 6 C[2] := 2 C[3] := 7

(*, *, *, *) 1 1 2 3 4 2 3 4

四皇后问题相当于在1~4的全排列中(4!=24)找 到一种排列符合条件。

(*, *, *, *) 1 1 (1, *, *, *) 2 3 4 * 2 3 4

(*, *, *, *) 1 (1, *, *, *) 2 3 (1, 3, *, *) 4

1 *

2

3 *

4

上图给出了四皇后问题的部分解答树,我们发现有 些结点无法继续扩展。例如,在(1,3,*,*)中,第3 行无论将皇后放到哪里,都会和第1行和第2行已放好 的皇后发生冲突,其他还未放置的皇后更是如此。

1. const maxn = 20; 2. var C: array[1..maxn] of integer; 3. n, tot : integer; 4. 5. 6. 7. 8. 9. 10. 11. procedure print; var i : integer; begin inc(tot); for i := 1 to n do write(C[i],' '); writeln; end;

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

procedure dfs(step:integer); var i, j : integer; ok : boolean; 用C[x]表示第x行皇后的列编号 begin 1 2 3 4 if step = n + 1 then 1 2 3 4 5 print else 2 3 4 5 6 for i := 1 to n do //枚举1~n列 3 4 5 6 7 begin ok := true; //局部临时变量回溯无需恢复现场 4 5 6 7 8 C[step] := i; for j := 1 to step-1 do //判断是否与前step-1个皇后冲突 if (C[step] = C[j]) or (step - C[step] = j - C[j]) or (step + C[step] = j + C[j]) then 14. begin 15. ok := false; 16. break; 17. end; 18. if ok = true then dfs(step+1); //不冲突,则继续尝试放置下一个皇后 19. end; 20. end;

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

procedure dfs(step:integer); var i, j : integer; ok : boolean; 用C[x]表示第x行皇后的列编号 begin 1 2 3 4 if step = n + 1 then 1 0 -1 -2 -3 print else 2 1 0 -1 -2 for i := 1 to n do //枚举1~n列 3 2 1 0 -1 begin ok := true; //局部临时变量回溯无需恢复现场 4 3 2 1 0 C[step] := i; for j := 1 to step-1 do //判断是否与前step-1个皇后冲突 if (C[step] = C[j]) or (step - C[step] = j - C[j]) or (step + C[step] = j + C[j]) then 14. begin 15. ok := false; 16. break; 17. end; 18. if ok = true then dfs(step+1); //不冲突,则继续尝试放置下一个皇后 19. end; 20. end;

1. begin 2. tot := 0; 3. readln(n); 4. dfs(1); //开始尝试放置第1个皇后 5. writeln(tot); 6. end.

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19.

procedure dfs(step:integer); //vis数组的确切含义是什么? var i : integer; //它表示已经放置的皇后占据了哪些列、 begin 主对角线和副对角线。 if step = n + 1 then 1 2 3 4 5 6 7 print 1 T else 2 T for i := 1 to n do //枚举1~n列 begin 3 T if (vis[1,i] = false) and (vis[2,step+i] = false) and (vis[3,step-i+n] = false) then begin C[step] := i; 1 2 3 4 vis[1,i] := true; 1 vis[2,step+i] := true; * vis[3,step-i+n] := true; 2 dfs(step+1); 3 vis[1,i] := false; vis[2,step+i] := false; 4 vis[3,step-i+n] := false; end;

? ?

例3:迷宫问题 描述:解救小哈。有一 天,小哈一个人去玩迷 宫,但是方向感不好的 小白就快就迷了路。小 哼得知后便立即去解救 无助的小哈。小哼当然 是有备而来,已经弄清 楚了迷宫的地图,现在 小哼要去解救小哈。问 题就此开始了……

? ?

? ? ? ? ? ? ? ? ? ? ?

例3:迷宫问题 已知迷宫由n行m列的单元格组成(n<=50,m<=50),每 个单元格要么是空地,要么是障碍物。注意:障碍物是不 能走的,当然小哼也不能走到迷宫之外。 任务1:帮助小哼找到从迷宫起点通往小哈所在位置的所 有方案数。 输入样例: 54 0010 0000 0010 0100 0001 1143 输出样例: 7

? ?

算法分析: 首先我们可以用一个二维数组来存储这个迷宫,用0 表示空地,1表示障碍物。假设刚开始的时候,小哼处 于迷宫的入口处(1,1),小哈在(4,3)。其实,就 是找从(1,1)走到(4,3)的所有路径 。如果你是小哼 ,你该怎么办呢? 4 1 1 2 1 ? 2 3 4

3

■ ■ ■
?

2
3 4 5



? ?

程序实现: dfs函数至少需维护2个参数,分别是当前这个点 的x坐标、y坐标。 1. procedure dfs(x:integer; y:integer) 2. begin 3. 4. end;

? 1. 2. 3. 4. 5. 6.

判断小哼是否已经到达小哈的位置: procedure dfs(x:integer; y:integer) begin //判断是否到达小哈的位置 if x = endx and y =endy then //如果可达 inc(tot); //可行方案数+1 end;

?

? ? ? ? ? ?

如果没有到达小哈的位置,则找出下一步可以走 的地方(规定顺时针方法尝试)。为了编程方便 ,我们不妨定义一个方向增量数组dir,如下: var dir : array[1..4,1..2] of integer = ((0,1), //向右走 (1,0), //向下走 (0,-1), //向左走 (-1,0) //向上走 );

?

1. 2. 3. 4. 5. 6.

通过这个方向增量数组,使用循环就很容易获得 下一步的坐标。这里我们将下一步的横坐标用nx 存储,纵坐标用ny存储。 //枚举四个方向的走法 for k := 1 to 4 do begin nx := x + dir[k,1]; //下一步的x坐标 ny := y + dir[k,2]; //下一步的y坐标 end;

?

?

接下来我们要对下一个点(nx,ny)事先进行判 断:是否越界?是否为障碍物?该点是否已经在 路径中(避免重复访问),为此需用used[nx,ny] 标记数组进行记录。 如果这个点符合上述所有要求,则对这个点进行 下一步的扩展,即dfs(nx,ny)

1. const maxn = 20; 2. var map : array[1..maxn,1..maxn] of integer; 3. used : array[1..maxn,1..maxn] of boolean; 4. dir : array[1..4,1..2] of integer = 5. ((0,1),(1,0),(0,-1),(-1,0)); 6. ans : integer; 7. n, m, startx, starty, endx, endy, i, j : integer; 8. tot : integer;

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.

procedure dfs(x:integer ; y:integer) var k : integer; nx, ny : integer; begin if (x = endx) and (y = endy) then inc(tot); else for k := 1 to 4 do begin nx := x + dir[k,1]; ny := y + dir[k,2]; if (nx < 1) or (nx > n) or (ny < 1) or (ny > m) then continue; if (map[nx,ny] = 0) and (used[nx,ny] = false) then begin used[nx,ny] := true; dfs(nx,ny); used[nx,ny] := false; end; end; end;

1. begin 2. fillchar(used,sizeof(used),false); 3. tot := 0; 4. readln(n,m); 5. for i := 1 to n do 6. for j := 1 to m do 7. read(map[i,j]); 8. readln(startx,starty,endx,endy); 9. used[startx,starty] := true; 10. dfs(startx,starty); 11. writeln(tot); 12. end.

?

任务2:打印小哼从迷宫的起点通往小哈所在位置 的所有路径。

输出样例: (1,1)->(1,2)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,3) (1,1)->(1,2)->(2,2)->(3,2)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(4,3) (1,1)->(1,2)->(2,2)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(4,3) (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,3) (1,1)->(2,1)->(2,2)->(3,2)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(4,3) (1,1)->(2,1)->(3,1)->(3,2)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,3) (1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(4,3)

1. const maxn = 20; 2. var map : array[1..maxn,1..maxn] of integer; 3. used : array[1..maxn,1..maxn] of boolean; 4. dir : array[1..4,1..2] of integer = 5. ((0,1),(1,0),(0,-1),(-1,0)); 6. route : array[0..maxn*maxn,1..2] of integer; 7. n, m, startx, starty, endx, endy, i, j : integer;

1. procedure dfs(x:integer; y:integer;step:integer); 2. var k : integer; 3. nx, ny : integer; 4. begin 5. if (x = endx) and (y = endy) then 6. print(step-1) 7. else 8. for k := 1 to 4 do 9. begin 10. nx := x + dir[k,1]; 11. ny := y + dir[k,2]; 12. if (nx < 1) or (nx > n) or (ny < 1) or (ny > m) then continue; //判断 是否越界 13. if (map[nx,ny] = 0) and (used[nx,ny] = false) then //判断是否为障碍 物,是否已访问过 14. begin 15. used[nx,ny] := true; 16. route[step,1] := nx; 17. route[step,2] := ny; 18. dfs(nx,ny,step+1); 19. used[nx,ny] := false; 20. end; 21. end; 22. end;

1. procedure print(step:integer); 2. begin 3. write('(',startx,',',starty,')->'); 4. for i := 0 to step-1 do 5. begin 6. write('(',route[i,1],',',route[i,2],')->'); 7. end; 8. writeln('(',route[step,1],',', route[step,2],')'); 9. end;

1. begin 2. fillchar(used,sizeof(used),false); 3. readln(n,m); 4. for i := 1 to n do 5. for j := 1 to m do 6. read(map[i,j]); 7. readln(startx,starty,endx,endy); 8. used[startx,starty] := true; 9. dfs(startx,starty,0); 10. end.

?
? ? ? ? ? ? ? ? ? ?

任务3:帮助小哼找到从迷宫起点通往小哈所在位 置花费的最少步数。 输入样例: 54 0010 0000 0010 0100 0001 1143 输出样例: 7

?

程序实现:

?

dfs函数至少需维护3个参数,分别是当前这个点 的x坐标、y坐标以及当前已经走过的步数step 1. procedure dfs(x:integer; y:integer; step:integer) 2. begin 3. 4. end;

? 1. 2. 3. 4. 5. 6. 7.

判断小哼是否已经到达小哈的位置: procedure dfs(x:integer; y:integer; step:integer) begin //判断是否到达小哈的位置 if (x = endx) and (y =endy) then if step < min then //更新步数最少值 min = step; end;

1. const maxn = 20; 2. var map : array[1..maxn,1..maxn] of integer; 3. used : array[1..maxn,1..maxn] of boolean; 4. dir : array[1..4,1..2] of integer = 5. ((1,0),(0,1),(0,-1),(-1,0)); 6. ans : integer; 7. n, m, startx, starty, endx, endy, i, j : integer;

1. procedure dfs(x:integer; y:integer; step:integer); 2. var k : integer; 3. nx, ny : integer; 4. begin 5. if (x = endx) and (y = endy) then 6. begin 7. if step < ans then 8. ans := step; 9. end

1. else 2. for k := 1 to 4 do 3. begin 4. nx := x + dir[k,1]; 5. ny := y + dir[k,2]; 6. if (nx < 1) or (nx > n) or (ny < 1) or (ny > m) then continue; //判断是否越界 7. if (map[nx,ny] = 0) and (used[nx,ny] = false) then //判断是否为障碍物,是否已访问过 8. begin 9. used[nx,ny] := true; 10. dfs(nx,ny,step+1); 11. used[nx,ny] := false; 12. end; 13. end; 14. end;

1. begin 2. fillchar(used,sizeof(used),false); 3. ans := 9999; 4. readln(n,m); 5. for i := 1 to n do 6. for j := 1 to m do 7. read(map[i,j]); 8. readln(startx,starty,endx,endy); 9. used[startx,starty] := true; 10. dfs(startx,starty,0); 11. writeln(ans); 12. end.

?
?
?

任务4:打印小哼找到一条从迷宫的起点通往小 哈所在位置的最短路径。 输出样例:
(1,1)->(1,2)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,3)
1 1 ? 2 3 4

■ ■ ■
?

2
3 4 5



1. const maxn = 20; 2. var map : array[1..maxn,1..maxn] of integer; 3. used : array[1..maxn,1..maxn] of boolean; 4. dir : array[1..4,1..2] of integer = 5. ((0,1),(1,0),(0,-1),(-1,0)); 6. route, route_ans : array[0..maxn*maxn,1..2] of integer; ans : integer;

7.

8. 9.

n, m, startx, starty, endx, endy, i, j : integer; flag : boolean;

1. procedure dfs(x:integer; y:integer; step:integer); 2. var k : integer; 3. nx, ny ,tx, ty : integer; 4. begin 5. if (x = endx) and (y = endy) then 6. begin 7. flag := true; 8. if step < ans then 9. begin 10. ans := step; 11. 12. 13. 14. 15. 16. 17. for i := 0 to step-1 do begin route_ans[i,1] := route[i,1]; route_ans[i,2] := route[i,2]; end; end; end

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

else for k := 1 to 4 do begin nx := x + dir[k,1]; ny := y + dir[k,2]; if (nx < 1) or (nx > n) or (ny < 1) or (ny > m) then continue; if (map[nx,ny] = 0) and (used[nx,ny] = false) then begin used[nx,ny] := true; book[step] := k; //记录方向 dfs(nx,ny,step+1); used[nx,ny] := false; end; end; end;

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.

else for k := 1 to 4 do begin nx := x + dir[k,1]; ny := y + dir[k,2]; if (nx < 1) or (nx > n) or (ny < 1) or (ny > m) then continue; if (map[nx,ny] = 0) and (used[nx,ny] = false) then begin used[nx,ny] := true; route[step,1] := nx; route[step,2] := ny; dfs(nx,ny,step+1); used[nx,ny] := false; end; end; end;

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21.

begin fillchar(used,sizeof(used),false); flag := false; ans := 9999; readln(n,m); for i := 1 to n do for j := 1 to m do read(map[i,j]); readln(startx,starty,endx,endy); used[startx,starty] := true; write('(',startx,',',starty,')->'); dfs(startx,starty,0); if flag = true then begin for i := 0 to ans-2 do write('(',route_ans[i,1],',',route_ans[i,2],')->'); writeln('(',route_ans[ans-1,1],',',route_ans[ans-1,2],')'); end else writeln('Impossible'); end.

? ?

拓展: 发明DFS算法的是John E. Hopcrosoft和 Robert E. Tarjan。当然他们并不是在研究全 排列或迷宫问题时发明了这个算法。1971~1972 年,他们在斯坦福大学研究图的连通性(任意两 点是否可以相互到达)和平面性(图中所有的边 互不交叉。在电路板上设计布线的时候,要求线 与线不能交叉,这就是平面性的一个实际应用) 发明了这个算法,他们也因此获得了1986年的 图灵奖。

?
?

例4:种子填充(floodfill)
描述:钓鱼岛由一个主岛和一些附属岛屿组成,小哼决定去钓鱼岛探 险。例如下图为钓鱼岛的航拍图:一个5行5列的字符矩阵,其中*标 号海洋,@表示岛屿。例如下图中有两个八连块。 任务1:小哼的飞机将会降落在(2,2)处,现在需要计算出小哼落地所 在岛的面积(即有多少个相邻的格子)。如果两个字符“@”所在的 格子相邻(横、竖、对角线),就说它们属于同一个岛屿。

?

输入样例: 5522 ****@ *@@*@ *@**@ @@@*@ @@**@

一般用DFS找 连通块:从指定@ 出发,递归遍历它 周围的@格子,每 访问一个格子,就 作一次访问标记。

1. const maxn = 10; 2. var map : array[1..maxn] of string; 3. used : array[1..maxn,1..maxn] of boolean; 4. n, m, i, j ,startx, starty: integer; 5. dir : array[1..8,1..2] of integer = 6. ((-1,0),(-1,1),(0,1),(1,1), 7. (1,0),(1,-1),(0,-1),(-1,-1)); 8. tot : integer;

1. 2. 3. 4. 5. 6. 7. 8. 9.

procedure dfs(x:integer; y:integer); var nx, ny : integer; k: integer; begin for k := 1 to 8 do begin nx := x + dir[k,1]; ny := y + dir[k,2]; if (nx < 1) or (nx > n) or (ny < 1) or (ny > m) then continue;

10. if (map[nx,ny] = '@') and (used[nx,ny] = false) then 11. begin 12. inc(tot); 13. used[nx,ny] := true; 14. dfs(nx,ny); 15. end; 16. end; 17. end;

1. begin 2. fillchar(used,sizeof(used),false); 3. readln(n,m,startx,starty); 4. for i := 1 to n do 5. readln(map[i]); 6. 7. tot := 1; 8. used[startx,starty] := true; 9. dfs(startx,starty); 10. writeln(tot); 11. end.

?

例4:种子填充(floodfill)

? 任务2:该钓鱼岛由多少个独立岛屿组成?
输入样例: 55 ****@ *@@*@ *@**@ @@@*@ @@**@ 从图中每个@出发,递归遍历它周围的@格子, 每访问一个格子,就作一次访问标记。

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

procedure dfs(x:integer; y:integer); var dx, dy, nx, ny : integer; k: integer; begin map[x,y] := '*'; //将现在所在位置替换为*

//循环遍历移动的8个方向 for dx := -1 to 1 do for dy := -1 to 1 do begin if (dx = 0) and (dy = 0) then continue; nx := x + dx; ny := y + dy; if (nx >= 1) and (nx <= n) and (ny >= 1) and (ny <= m) and (map[nx,ny] = '@') then 14. dfs(nx,ny); 15. end; 16. end;

1. 2. 3. 4. 5.

begin readln(n,m); for i := 1 to n do readln(map[i]); tot := 0;

6. 7. 8. 9. 10. 11. 12.

for i := 1 to n do for j := 1 to m do if map[i,j] = '@' then //从有@的地方开始dfs begin dfs(i,j); inc(tot); end;

13. writeln(tot); 14. end.

1. procedure dfs(x:integer; y:integer;color:integer); 2. var nx, ny : integer; 3. dx, dy : integer; 4. begin 5. for dx := -1 to 1 do 6. for dy := -1 to 1 do 7. begin 8. if (dx = 0) and (dy = 0) then continue; 9. nx := x + dx; 10. ny := y + dy; 11. if (nx < 1) or (nx > n) or (ny < 1) or (ny > m) then continue;

12. if (map[nx,ny] = '@') and (used[nx,ny] = false) then 13. begin 14. used[nx,ny] := true; 15. map[nx,ny] := chr(color + ord(‘0’)); //用字符1~给联通块编号 16. dfs(nx,ny,color); 17. end; 18. end; 19. end;

1. 2. 3. 4. 5.

begin fillchar(used,sizeof(used),false); readln(n,m); for i := 1 to n do readln(map[i]);

6. 7. 8. 9. 10. 11. 12. 13.

cnt := 0; //连通块编号 for i := 1 to n do for j := 1 to m do if (map[i,j] = '@') and (used[i,j] = false) then begin inc(cnt); dfs(i,j,cnt); end;

2 ****1 *22*1 *2**1 222*1 22**1

14. writeln(cnt); 15. end.

? ?

例5:跳马问题(骑士巡游问题) 描述:在n行m列的棋盘上,有一只中国象棋的 马,从某点例如(1,1)出发,按日字跳马,它可 以朝8个方向跳,但不允许出界或跳到已经跳过 的格子上,要求跳遍整个棋盘。输出总方案数, 并打印出前5种方案。

1. const maxn = 20; 2. var map : array[1..maxn,1..maxn] of integer; 3. used : array[1..maxn,1..maxn] of boolean; 4. dir : array[1..8,1..2] of integer = 5. ((1,-2),(2,-1),(2,1),(1,2), 6. (-1,2),(-2,1),(-2,-1),(-1,-2)); 7. n, m, startx, starty : integer; 8. tot : integer;

1. procedure dfs(x:integer; y:integer; step:integer); 2. var i, j , k, nx, ny : integer; 3. begin 4. if step > n * m then 5. begin 6. inc(tot); 7. if tot <= 5 then //打印前5种方案 8. begin 9. writeln; 10. for i := 1 to n do 11. begin 12. for j := 1 to m do 13. write(map[i,j],' '); 14. writeln; 15. end; 16. end; 17. end

1. 2. 3. 4. 5. 6.

else for k := 1 to 8 do begin nx := x + dir[k,1]; ny := y + dir[k,2]; if (nx < 1) or (nx > n) or (ny < 1) or (ny > m) then continue;

7. if (map[nx,ny] = 0) and (used[nx,ny] = false) then 8. begin 9. used[nx,ny] := true; 10. map[nx,ny] := step; 11. dfs(nx,ny,step+1); 12. used[nx,ny] := false; 13. map[nx,ny] := 0; 14. end; 15. end; 16. end;

1. begin 2. tot := 0; 3. readln(n,m,startx,starty); 4. 5. 6. map[startx,starty] := 1; used[startx,starty] := true; dfs(startx,starty,2); //开始尝试填充2

7. writeln(tot); 8. end.

拓展:马拦过河卒
?

棋盘上A点有一个过河卒,需要走到目标B点。卒行走的 规则:可以向下、或者向右。同时在棋盘上C点有一个对方 的马,该马所在的点和所有跳跃一步可达的点称为对方马的 控制点。因此称之为“马拦过河卒”。
-2 1 -2 -1 -1 -2 -1 2 1 -2 12 21 2 -1

? 棋盘用坐标表示,A点(0, 0)、B点(n, m)(n, m为 不超过20的整数),同样马的位置坐标是需要给 出的。现在要求你计算出卒从A点能够到达B点 的路径的条数,假设马的位置是固定不动的,并 不是卒走一步马走一步。 ? 【输入】 ? 一行四个数据,分别表示B点坐标和马的坐 标。 ? 【输出】 ? 一个数据,表示所有的路径条数。 ? 【样例输入】 ? 6632 ? 【样例输出】 ? 17

1. const maxn = 20; 2. var map : array[0..maxn,0..maxn] of integer; 3. vis : array[0..maxn,0..maxn] of boolean; 4. dir : array[1..8,1..2] of integer = 5. ((-2,-1),(-2,1),(-1,-2),(-1,2), 6. (1,-2),(1,2),(2,-1),(2,1)); //马的控制方向 7. n, m, k, horsex, horsey, nx, ny : integer; 8. tot : integer;

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21.

procedure dfs(x:integer;y:integer); var k, nx, ny : integer; dir : array[1..2,1..2] of integer = ((1,0),(0,1)); //卒行走方向 begin if (x = n) and (y = m) then inc(tot) else begin for k := 1 to 2 do begin nx := x + dir[k,1]; ny := y + dir[k,2]; if (nx >= 0) and (nx <= n) and (ny >=0) and (ny <= m) and (map[nx,ny] = 0) and (vis[nx,ny] = false) then begin vis[nx,ny] := true; dfs(nx,ny); vis[nx,ny] := false; end; end; end; end;

1. 2. 3.

begin fillchar(map,sizeof(map),0); tot := 0;

4. readln(n,m,horsex,horsey); 5. vis[0,0] := true; 6. //将马的控制点设置-1 7. map[horsex,horsey] := -1; 8. for k := 1 to 8 do 9. begin 10. nx := horsex + dir[k,1]; 11. ny := horsey + dir[k,2]; 12. map[nx,ny] := -1; 13. end; 14. dfs(0,0); 15. writeln(tot); 16. end.

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

例6:数的划分 任何一个大于1的自然数n,总可以拆分成若干个小 于n的自然数之和。 输入样例:7 输出样例 7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4

1. procedure dfs(sum:integer; step:integer); 2. //sum表示待拆分的数, step表示第几步划分 3. var i : integer; 4. begin 5. if sum = 0 then 6. begin 7. write(n,'='); 8. for i := 1 to step - 2 do 9. write(a[i],'+'); 10. writeln(a[step-1]); 11. end 12. else 13. ……

1. else 2. for i := a[step-1] to sum do 3. //枚举填数i要不小于前一个数,且不超过剩余的sum 4. begin 5. if i < n then //不允许出现 n = n的情况 6. begin 7. a[step] := i; 8. sum := sum - i; 9. dfs(sum,step+1); 10. sum := sum + i; 11. end; 12. end; 13. end;

1. begin 2. readln(n); 3. a[0] := 1; //最小的子数为1 4. dfs(n,1); 5. end.

? ?

例7:分书问题 描述:学校放寒假时,信息学辅导教师有n本书 要分给参加培训的n个学生。如:A,B,C,D ,E共5本书要分给参加培训的张、刘、王、李、 孙5位学生,每人只能选1本。教师事先让每个人 将自己喜爱的书填写在如下的表中,然后根据他 们填写的表来分配书本,希望设计一个程序帮助 教师求出可能的分配方案,使每个学生都满意。

?

例7:分书问题

A 张

B

C ?

D ?

E


刘 孙 李

?

?
? ? ? ? ?

? ? ?

?

例7:分书问题 输入格式:第一行一个数n(学生的个数,书的 数量) 以下共n行,每行n个0或1(由空格隔开), 第i行数据表示第i个同学对所有书的喜爱情况。0 表示不喜欢该书,1表示喜欢该书。 输出格式:依次输出每个学生分到的书号。

A B C D E ?? 张 王? ? 刘 ?? ? 孙 ? 李 ?

输入样例: ? 5 ? 00110 ? 11000 ? 01100 ? 00010 ? 01001 输出样例: ? 31245

1. procedure dfs(step:integer);{搜索第step个人可以借的 书号} 2. var i:integer; 3. begin 4. if step=n+1 then 输出结果 5. else 6. for i:=1 to n do //枚举1~n本书 7. if 第 i 本书可借 then 8. begin 9. book[step] := i; 10. 标记第i本数已被借; 11. dfs(step+1); 12. 删除第i本书的被借标志; 13. 恢复book[step]值为空; 14. end; 15. end;

1. const maxn = 10; 2. var a : array[1..maxn,1..maxn] of integer; 3. book : array[1..maxn] of integer; 4. used : array[1..maxn] of boolean; 5. n, i, j : integer;

1. procedure dfs(step:integer); 2. var i : integer; 3. begin 4. if step = n + 1 then 5. begin 6. for i := 1 to step-1 do 7. write(book[i],' '); 8. writeln; 9. end 10. else

1. else 2. for i := 1 to n do //枚举n本书 3. begin 4. if (a[step,i] = 1) and (used[i] = false) then 5. begin 6. book[step] := i; 7. used[i] := true; 8. dfs(step+1); 9. used[i] := false; 10. book[step] := 0; 11. end; 12. end; 13. end;

? ?

?

例8:覆盖问题 描述:边长为N(偶数)的正方形,用N*N/2个 长为2宽为1的长方形将它全部覆盖。编程打印所 有覆盖方法。 当N=4时几种覆盖方法的打印格式举例如下:

?

? 1.

2.

3.

4. 5.

分析:把边长为n的正方形划分为 n*n个边长为1的格子,用 数组 a描述覆盖情况: a[i,j] =0:格子还没被覆盖,否 则被编号为a[i,j]的1*2格子覆盖. 算法描述: 先行后列的原则找到一个a[i,j]=0,即未被覆盖的格子 (i,j); 如果行号 (i<n)and(a[i+1,j]=0), 即正下方的格子未覆盖 , 那么格子 (i,j) 和 (i+1,j) 用同一个 1*2 的格子覆盖 . 转 向 4; 如果列号 (j<n)and(a[i,j +1 ]=0), 即右邻的格子未覆盖 , 那么格子 (i,j) 和 (i,j +1 ) 用同一个 1*2 的格子覆盖 . 转向 4; 如果已用完了n*n/2长方形,则转向5,否则执行1 打印现有的覆盖方案,得到一种覆盖方法。

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.

const maxn = 10; var a : array[1..maxn,1..maxn] of integer; n: integer; tot : integer; procedure print; var i, j : integer; begin writeln; inc(tot); for i := 1 to n do begin for j := 1 to n do write(a[i,j]); writeln; end; end;

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

procedure dfs(step:integer); //尝试用编号为step的1*2长方形 覆盖 var i, j, x, y : integer; flag : boolean; begin flag := false; //{先行后列找a[i,j]=0的格子} for i := 1 to n do begin if flag = true then break; for j := 1 to n do if a[i,j] = 0 then begin x := i; y := j; flag := true; break; end; end;

1. a[x,y] := step; {格子(x,y)用编号i覆盖} 2. if (x < n) and (a[x+1,y] = 0) then 3. {正下方格子未覆盖,用i覆盖} 4. begin 5. a[x+1,y] := step; 6. if step * 2 >= n * n then {最大编号为n*n/2} 7. print 8. else 9. dfs(step+1); 10. a[x+1,y] := 0; {回溯} 11. end;

1. if (y < n) and (a[x,y+1] = 0) then {右方方格子未 覆盖,用i覆盖} 2. begin 3. a[x,y+1] := step; 4. if step * 2 >= n * n then 5. print 6. else 7. dfs(step+1); 8. a[x,y+1] := 0; {回溯} 9. end; 10. a[x,y] := 0; {回溯} 11. end;

1. begin 2. fillchar(a,sizeof(a),0); 3. readln(n); 4. dfs(1); 5. writeln(tot); 6. end.

? ?

? ? ? ? ?

例9:0/1背包问题 描述:给定n中物品和一背包,物品i的重量是wi ,其价值为vi,背包的容量为C。如应如何选择 装入背包的物品,使得装入背包中物品的总价值 最大? 输入 4 8 1423 2143 输出 1 0 1 1 分析:整个解的空间相当于一个二叉树,左边是 0,代表不取这个物品,右边是1,代表取这个物 品,然后进行DFS。

1. 2. 3. 4. 5. 6. 7. 8.

const maxn = 1000; var v, w : array[1..maxn] of integer; //所有物品的价值;物品的重量; x, bestx : array[1..maxn] of integer; //x暂存各物品的选中情况;物品的选中情况0/1 n, TotCap, bestval : integer; //物品的个数,背包的容量,最大价值 i : integer;

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

procedure dfs(cv:integer; cw:integer; step:integer); //进行第 step种物品选择 //cw当前包内物品重量,cv当前包内物品价值 var i, k : integer; begin if step = n + 1 then begin if cv > bestval then begin bestval := cv; for i := 1 to n do bestx[i] := x[i]; end; end else

1. begin 2. for k := 0 to 1 do //枚举step物品的选择状态:0选、1 不选 3. begin 4. x[step] := k; //存储step物品的选择状态 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. if cw + x[step] * w[step] <= TotCap then begin cw := cw + w[step] * x[step]; cv := cv + v[step] * x[step]; dfs(cv,cw,step+1); cw := cw - w[step] * x[step]; cv := cv - v[step] * x[step]; end; end; end;

1. begin 2. bestval := 0; 3. readln(n,TotCap); 4. 5. 6. 7. for i := 1 to n do read(w[i]); for i := 1 to n do read(v[i]); dfs(0,0,1); writeln(bestval);

8. for i := 1 to n do write(bestx[i]); 9. writeln; 10. end.

? ?

例10:素数方阵 描述:将1~n*n的数填充至一n*n矩阵中,使得 任意一个数与其相邻的数的和为素数。

输入:n = 5 输出: 1 2 3 4 6 5 8 15 25 18 23 14 16 13 24 17 21 10 19 12

7 22 9 20 11

回顾
? ? ? ? ? ? ? ? ? 栈与递归 回溯法 深度优先搜索代码框架(全排列) 经典例题 1、八皇后 6、图形覆盖问题 2、迷宫问题 7、自然数拆分问题 3、跳马问题 …… 4、Floodfill问题 5、0/1背包问题


深度优先搜索的基本思想

深度优先搜索的基本思想搜索是人工智能中的一种基本方法,也是信息学竞赛选手所必须熟练掌握的 一种方法,它最适合于设计基于一组生成规则集的问题求解任务,每个新的...

有界深度优先搜索算法的实现

实验报告 一.实验目的 有界深度优先搜索算法的实现 (1)熟悉盲目搜索—有界深度优先算法; (2)通过实验实际操作有界深度优先算法的运行,深入理解其内涵; (3)掌握...

数据结构实验报告(三):实现深度优先搜索与广度优先搜索算法

数据结构实验报告(三):实现深度优先搜索与广度优先搜索算法_计算机软件及应用_IT/计算机_专业资料。数据结构实验报告(三):实现深度优先搜索与广度优先搜索算法课程...

二叉树的广度优先搜索和深度优先搜索

二叉树的广度优先搜索和深度优先搜索_互联网_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 二叉树的广度优先搜索和深度优先搜索_互联网_IT/计算机_专业...

图深度优先搜索C++

深度优先搜索C++_IT/计算机_专业资料。DFS的C++实现#include<iostream> using namespace std; #define NULL 0 #define MaxSize 20 struct edgenode 结点 { int...

广度优先搜索和深度优先搜索

有两种常用的方法可用来搜索图: 即深度优先搜索和广度优先搜索。 它们最终都会到达所有 连通的顶点。深度优先搜索通过栈来实现,而广度优先搜索通过队列来实现。 深度...

实验4 无向图的深度优先搜索

实验4 无向图的深度优先搜索_化学_自然科学_专业资料。设无向图G有n个点e条边,写一算法建立G的邻接多表,并按照深度优先搜索输出顶点,要求该算法时间复杂性为O...

答深度优先搜索算法的特点是

习题3 1、答:深度优先搜索算法的特点是 ①一般不能保证找到最优解; ②当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制; ③方法与问题无关,具有...

深度优先搜索举例

深度优先搜索 19页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 深度优先搜索举例 隐藏>> 卒子穿阵问题。如图...

图的深度优先遍历实验报告

假设初始状态时图中所有顶 点未曾访问,则深度优先搜索可从图中某个顶点 v 出发,访问此顶点, 然后依次从 v 的未被访问的邻接点出发深度优先遍历图, 直至图中...