深度优先搜索ppt课件.ppt

《深度优先搜索ppt课件.ppt》由会员分享，可在线阅读，更多相关《深度优先搜索ppt课件.ppt（135页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物栈与递归我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例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

2、.我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物要理解递归，首先应了解一种数据结构：堆要理解递归，首先应了解一种数据结构：堆栈（简称栈）的概念。栈（简称栈）的概念。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物栈（栈（stack）又名堆栈，它是一种运算受限的线性表。）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一其限制是仅允许在表的一端进行插入和删除运算。这一端称为栈顶，相对地，

3、把另一端称为栈底。向一个栈插端称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素称作进栈、入栈或压栈；从一个栈删除元素又入新元素称作进栈、入栈或压栈；从一个栈删除元素又称作出栈或退栈。称作出栈或退栈。 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物栈指针top123Init初始化栈初始化栈Procedure init;Begin top := 0;End;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物栈指针top

4、123Push入栈入栈Procedure push(x:integer);Begin top := top + 1; if isfull = false then Stacktop := x; else writeln(stack full);End;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物栈指针top123Isfull判栈满判栈满Function isfull;Begin if top = n + 1 then; isfull := true; else isfull := false;End;n

5、 + 1我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物栈指针top123Gettop取栈顶元素取栈顶元素Function gettop:integerBegin gettop : = stacktop;End;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物栈指针top123Push出栈出栈Procedure pop;Begin if isempty = true then write(stack empty) els

6、e top : = top 1;End;栈空栈空我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物栈指针top123Isempty判栈空判栈空Function isempty;Begin if top = 0 then; isempty := true; else isempty := false;End;0我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例0-2：输入n个整数，并逆序输出（栈实现）。输入样例：31 2 3

7、输出样例：3 2 1我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物const maxn = 20;var stack : array1.maxn of integer; top : integer; n, i, x : integer;procedure init;begin top := 0;end;function isfull:boolean;begin if top = n + 1 then isfull := true else isfull := false;end;我吓了一跳，蝎子是多么丑恶

8、和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物function isempty:boolean;begin if top = 0 then isempty := true else isempty := false;end;procedure push(x:integer);begin top := top + 1; if isfull = true then writeln(Stack Full) else stacktop := x;1.end;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是

9、我也感到愉快，证实我的猜测没有错：表里边有一个活的生物function gettop:integer;begin gettop := stacktop;end;procedure pop;begin if isempty = true then writeln(Stack Empty) else top := top - 1;1.end;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物begin readln(n); for i := 1 to n do begin read(x); push(x); en

10、d; while isempty true do begin write(gettop, ); pop; end;1.end.我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物编译器处理函数调用时，就是使用栈来保存数据的。当主调函编译器处理函数调用时，就是使用栈来保存数据的。当主调函数调用另一个函数时，编译器将主调函数的所有实参和返回地数调用另一个函数时，编译器将主调函数的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。址压入到栈中，栈指针将移到合适的位置来容纳这些数据。Function

11、函数1:integer;Begin 函数2；End;函数函数1调用函数调用函数2系统栈中的变化（入栈）系统栈中的变化（入栈）我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物当进行被调函数时，编译器将栈中的实参数据弹出，赋值给函当进行被调函数时，编译器将栈中的实参数据弹出，赋值给函数的形参。在被调用函数执行期间，还可利用栈来保存函数执数的形参。在被调用函数执行期间，还可利用栈来保存函数执行时的局部变量。当被调用函数准备返回时，系统将弹出栈中行时的局部变量。当被调用函数准备返回时，系统将弹出栈中所有当前函数压入

12、栈中的值，这时，栈指针移动到被调用函数所有当前函数压入栈中的值，这时，栈指针移动到被调用函数刚开始执行时的位置。接着被调用函数返回，系统从栈中弹出刚开始执行时的位置。接着被调用函数返回，系统从栈中弹出返回地址，主调函数就可以继续执行了。返回地址，主调函数就可以继续执行了。函数函数2返回至函数返回至函数1系统栈中的变化（出栈）系统栈中的变化（出栈）我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物回到阶乘的递归算法上来。假设要计算回到阶乘的递归算法上来。假设要计算5的阶乘，通过前面设的阶乘，通过前面设计的递归程

13、序执行过程如下。计的递归程序执行过程如下。首先，在主函数中调用首先，在主函数中调用fact(5)函数，将返回地址、参数、局部函数，将返回地址、参数、局部变量压入堆栈。变量压入堆栈。 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物在在fact()函数中，判断函数中，判断n的值若不为的值若不为0，则递归调用，则递归调用fact(4)，这时将函数的返回地址和参数压入堆栈。，这时将函数的返回地址和参数压入堆栈。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的

14、猜测没有错：表里边有一个活的生物程序继续递归调用时，将程序继续递归调用时，将fact(3)、fact(2)、fact(1)逐步压入堆栈逐步压入堆栈我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物当调用当调用fact(0)时，达到阶乘递归算法的结束条件，时，达到阶乘递归算法的结束条件，这时结束这时结束fact(0)函数调用，从堆栈中弹出该层的相函数调用，从堆栈中弹出该层的相关数据，并返回函数的结果关数据，并返回函数的结果1。这时栈顶中保存的将。这时栈顶中保存的将是是fact(1)中的相关数据中的相关数据我吓了

15、一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物当递归函数逐层返回时，栈中压入的数据将逐步弹当递归函数逐层返回时，栈中压入的数据将逐步弹出，当弹出出，当弹出fact(4)后的栈结果如图所示后的栈结果如图所示我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物当函数当函数fact(5)返回时得到返回时得到5的阶乘等于的阶乘等于120，同时从，同时从栈中弹出调用函数时的数据，完成整个递归调用，栈中弹出调用函数时的数据，完成整个递归调用

16、，并返回主函数输出执行。并返回主函数输出执行。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物搜索深度优先搜索一、算法模型二、经典应用我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物一、引例 例1：输入一个数n，按字典序从小到大的顺序输出1n的全排列。两个序列的字典序大小关系等价于从开始的第一个不相同位置处的大小关系。例如，（1,3,2） (2,1,3) 当n = 3时，所有排序的排序结果是（1,2,3）、（1,3,2）

17、、（2,1,3）、（2,3,1）、（3,1,2）、（3,2,1）。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物一、引例 方法一 var a, b, c : integer; begin for a := 1 to 3 do for b := 1 to 3 do for c := 1 to 3 do begin if (a b) and (b c) and (c a) then writeln(a, ,b, ,c); end; end.我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世

18、界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 方法一、穷举法方法一、穷举法 寻找问题解的一种可靠的方法是首先寻找问题解的一种可靠的方法是首先列出所有可能候选解，然后依次检查每一个，列出所有可能候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过在实际应用中，很少使述方法是可行的。不过在实际应用中，很少使用这种方法，因为候选解的数量通常都非常

19、大用这种方法，因为候选解的数量通常都非常大，即便采用最快的计算机也只能解决规模很小，即便采用最快的计算机也只能解决规模很小的问题。的问题。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 方法二 这里我们先将这个问题形象化，举个例子，假设有编号为1、2、3的3张扑克牌和编号为1、2、3的3个盒子。现在需要将这3张扑克牌分别放到3个盒子里面，并且每个盒子有且只能放一张扑克牌，那么一共有多少种不同的方法呢？我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜

20、测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶

21、和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物一、引例 方法二、回溯法 从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到“ 尽头 ”而没达到目的地的时候, 再倒回上一个出发点, 从另一个可能出发, 继续搜索. 这种不断“ 倒回 一步寻找解的方法, 称作 回溯法 .我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的

22、猜测没有错：表里边有一个活的生物程序实现程序实现我们先来解决最基本的问题：如何往小盒子中放扑克牌。每一个小盒子都可能放1号、2号或者3号扑克牌，这需要一一尝试，用一个for循环即可解决。for i := 1 to n do /枚举1n张牌 astep := i; /将i号扑克牌放入到第step个盒子中分析：数组a用来表示小盒子，变量step表示当前正处在第step个小盒子面前。astep := i; 表示将i号扑克牌放入到第step个盒子中。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物这里有一个问题：如

23、果判断该扑克牌是否还在手中，而没这里有一个问题：如果判断该扑克牌是否还在手中，而没有放入其他盒子中？有放入其他盒子中？for i = 1 to n dobegin If usedi = false then /如果i号扑克牌仍在手中 begin astep := i; /将i号扑克牌放入到第step个盒子中 usedi := true; /标记i号扑克牌已不在手中 end;1. end;123FFF123TFF123TTF我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物OK，现在已经处理完第step个小盒子

24、了，接下来需要往下走一步，继续处理第step+1盒小盒子，处理方法与第step步完全相同。因此我们不妨将刚才处理第step个小盒子的代码封装为一个函数，函数的名字就叫做dfs吧！procedure dfs(step:integer)begin for i := 1 to n do begin If usedi = false begin astep := i; usedi := true; end; end;1.end;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物由此，处理第step个盒子，我们可调用d

25、fs(step)完成，而处理第step+1个盒子，就是dfs(step+1)由此我们不妨使用函数的递归调用加以实现。procedure dfs(step:integer)begin for i := 1 to n do begin if usedi = false begin astep := i; usedi := true; dfs(step+1); /继续尝试第继续尝试第step+1个盒子个盒子 usedi = false; /取回刚刚尝试的那张牌取回刚刚尝试的那张牌 end; end;1.end;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到

26、愉快，证实我的猜测没有错：表里边有一个活的生物再次提醒：如果在回溯法中使用了辅助的全局变量，一定要及时把它们恢复原状！特别地，若函数有多个出口，则需在每个出口处恢复被修改的值。123TTTdfs(step)dfs(step+1)递归调用递归调用123TTF我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物再次提醒：如果在回溯法中使用了辅助的全局变量，一定要及时把它们恢复原状！特别地，若函数有多个出口，则需在每个出口处恢复被修改的值。123TTTdfs(step)dfs(step+1)回溯回溯123TTF我吓了

27、一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物还剩下最后一个问题：就是什么时候输出一个满足要求的序列呢？其实当我们处理到第n+1个小盒子的时候（即step等于n+1），说明前n个盒子都已经放好扑克牌了，这时将1n个小盒子中的扑克牌编号打印出来即可。procedure dfs(step:integer)begin if step = n+1 then print;else for i := 1 to n do 1. end;step = n + 1我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽

28、的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物const maxn = 20;var a : array1.maxn of integer; used : array1.maxn of boolean; n : integer;procedure print;var i : integer;begin for i := 1 to n do write(ai, ); writeln;end; 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物procedure dfs(step:inte

29、ger);var i : integer;begin if step = n + 1 then print else for i := 1 to n do begin if usedi = false then begin astep := i; usedi := true; dfs(step+1); usedi := false; end; end;end; 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物begin fillchar(used,sizeof(used),false); readln(n)

30、; dfs(1);end. 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物算法框架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);1.end.我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里

31、呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物深度优先搜索（深度优先搜索（Depth First Search，DFS）主要思想：不撞南墙不回头主要思想：不撞南墙不回头深度优先遍历的主要思想就是：首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问。沿着某条路径遍历直到末端，然后回溯，再沿着另一条进行同样的遍历，直到所有的顶点都被访问过为止。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的

32、生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物分析：通过图例可以非常直观的了解深度优先搜索的工作方式。下面来分析一下如何用代码来实现它。 大家都知道，深度优先的主要思想就是“不撞南墙不回头”，“一条路走到黑”，如果遇到“墙”或者“无路可走”时再去走下一条路。所以先规定好一个走路的规则，比如就按照右下左上顺时针的方式去尝试。如上图僵尸的位置是起始点，先往右走，但是有堵墙走不了，所以按照规定尝试往下走。到达“1”的位置，此时重复刚才的步骤，先向右走可以走到“2”，再重复规则发现向右可以走到“3”，再重复发

33、现“下右左上”四个方向都不能走，这时候就退回“2”的位置尝试向下走。依次类推直到走到最终的目的地。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物二、经典问题例例2：八皇后问题：八皇后问题描述：在棋盘上放置8个皇后，使得它们互不攻击，此时每个皇后的攻击范围为同行同列和同对角线，要求找出所有解。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物二、经典问题例2：八皇后问题不难发现以下事实：恰好每行每列各放置一个皇后。如果用C

34、x表示第x行皇后的列编号，则问题变成了全排列生成问题。而18的排列一共只有8! = 40320个，枚举量不会超过它。C1 := 6C2 := 2C3 := 7我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物 四皇后问题相当于在四皇后问题相当于在14的全排列中（的全排列中（4！=24）找）找到一种排列符合条件。到一种排列符合条件。（*, *, *, *）1 12 23 34 41 12 23 34 4我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没

35、有错：表里边有一个活的生物（*, *, *, *）（1, *, *, *）1 12 23 34 41 1* *2 23 34 4我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物（*, *, *, *）（1, *, *, *）1 12 23 34 41 1* *2 2* * 3 34 4（1, 3, *, *） 上图给出了四皇后问题的部分解答树，我们发现有图给出了四皇后问题的部分解答树，我们发现有些结点无法继续扩展。例如，在（些结点无法继续扩展。例如，在（1,3，*，*）中，第）中，第3行无论将皇后放到哪里，

36、都会和第行无论将皇后放到哪里，都会和第1行和第行和第2行已放好行已放好的皇后发生冲突，其他还未放置的皇后更是如此。的皇后发生冲突，其他还未放置的皇后更是如此。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物const maxn = 20;var C: array1.maxn of integer; n, tot : integer;procedure print;var i

37、 : integer;begin inc(tot); for i := 1 to n do write(Ci, ); writeln;end; 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物procedure dfs(step:integer);var i, j : integer; ok : boolean;begin if step = n + 1 then print else for i := 1 to n do /枚举1n列 begin ok := true; /局部临时变量回溯无需恢复现场 C

38、step := i; for j := 1 to step-1 do /判断是否与前step-1个皇后冲突 if (Cstep = Cj) or (step - Cstep = j - Cj) or (step + Cstep = j + Cj) then begin ok := false; break; end; if ok = true then dfs(step+1); /不冲突，则继续尝试放置下一个皇后 end;end;123412345234563456745678用Cx表示第x行皇后的列编号我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到

39、愉快，证实我的猜测没有错：表里边有一个活的生物procedure dfs(step:integer);var i, j : integer; ok : boolean;begin if step = n + 1 then print else for i := 1 to n do /枚举1n列 begin ok := true; /局部临时变量回溯无需恢复现场 Cstep := i; for j := 1 to step-1 do /判断是否与前step-1个皇后冲突 if (Cstep = Cj) or (step - Cstep = j - Cj) or (step + Cstep = j

40、 + Cj) then begin ok := false; break; end; if ok = true then dfs(step+1); /不冲突，则继续尝试放置下一个皇后 end;end;123410-1-2-3210-1 -23210-143210用Cx表示第x行皇后的列编号我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物begin tot := 0; readln(n); dfs(1); /开始尝试放置第1个皇后 writeln(tot);end. 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为

41、什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物procedure dfs(step:integer);var i : integer;begin if step = n + 1 then print else for i := 1 to n do /枚举1n列 begin if (vis1,i = false) and (vis2,step+i = false) and (vis3,step-i+n = false) then begin Cstep := i; vis1,i := true; vis2,step+i := true; vis3,

42、step-i+n := true; dfs(step+1); vis1,i := false; vis2,step+i := false; vis3,step-i+n := false; end; end;end;/vis数组的确切含义是什么？/它表示已经放置的皇后占据了哪些列、主对角线和副对角线。12341* *23412345671T T 2 T T 3 T T 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例3：迷宫问题描述：解救小哈。有一天，小哈一个人去玩迷宫，但是方向感不好的小白就快就迷了路。小

43、哼得知后便立即去解救无助的小哈。小哼当然是有备而来，已经弄清楚了迷宫的地图，现在小哼要去解救小哈。问题就此开始了我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例3：迷宫问题已知迷宫由n行m列的单元格组成（n=50,m=50），每个单元格要么是空地，要么是障碍物。注意：障碍物是不能走的，当然小哼也不能走到迷宫之外。任务1：帮助小哼找到从迷宫起点通往小哈所在位置的所有方案数。输入样例：5 40 0 1 00 0 0 00 0 1 00 1 0 00 0 0 11 1 4 3输出样例：7我吓了一跳，蝎子是多么丑

44、恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物算法分析：首先我们可以用一个二维数组来存储这个迷宫，用0表示空地，1表示障碍物。假设刚开始的时候，小哼处于迷宫的入口处（1,1），小哈在（4,3）。其实，就是找从（1,1）走到(4，3)的所有路径 。如果你是小哼，你该怎么办呢？ 1 12 23 34 41 1 2 23 3 4 4 5 5 1234我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物程序实现：程序实现：dfs函数至少需维护2个参数，分

45、别是当前这个点的x坐标、y坐标。procedure dfs(x:integer; y:integer) begin 1. end; 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物判断小哼是否已经到达小哈的位置：procedure dfs(x:integer; y:integer)begin/判断是否到达小哈的位置if x = endx and y =endy then /如果可达 inc(tot); /可行方案数+11.end; 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢

46、？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物如果没有到达小哈的位置，则找出下一步可以走的地方（规定顺时针方法尝试）。为了编程方便，我们不妨定义一个方向增量数组dir，如下：var dir : array1.4,1.2 of integer = (0,1), /向右走 (1,0), /向下走 (0,-1), /向左走 (-1,0) /向上走 ); 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物通过这个方向增量数组，使用循环就很容易获得下一步的坐标。这里我们将下一步的横坐标用nx存储，纵坐标用

47、ny存储。/枚举四个方向的走法for k := 1 to 4 dobeginnx := x + dirk,1; /下一步的x坐标ny := y + dirk,2; /下一步的y坐标1.end; 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物接下来我们要对下一个点（nx,ny）事先进行判断：是否越界？是否为障碍物？该点是否已经在路径中（避免重复访问），为此需用usednx,ny标记数组进行记录。如果这个点符合上述所有要求，则对这个点进行下一步的扩展，即dfs(nx,ny) 我吓了一跳，蝎子是多么丑恶和恐怖的

48、东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物const maxn = 20;var map : array1.maxn,1.maxn of integer; used : array1.maxn,1.maxn of boolean; dir : array1.4,1.2 of integer = (0,1),(1,0),(0,-1),(-1,0); ans : integer; n, m, startx, starty, endx, endy, i, j : integer; tot : integer; 我吓了一跳，蝎子是多么丑恶和恐

49、怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物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 + dirk,1; ny := y + dirk,2; if (nx n) or (ny m) then continue; if (mapnx,ny = 0) and (use

50、dnx,ny = false) then begin usednx,ny := true; dfs(nx,ny); usednx,ny := false; end; end;end; 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物begin fillchar(used,sizeof(used),false); tot := 0; readln(n,m); for i := 1 to n do for j := 1 to m do read(mapi,j); readln(startx,starty,end