全国青少年信息学奥林匹克竞赛NOI信息学-递归与深度优先搜索DFSPowerPoint 演示文稿

1、1递归与深度优先搜索递归与深度优先搜索2迷宫求解迷宫求解31、迷宫求解、迷宫求解-定义数据结构，读取迷宫信息定义数据结构，读取迷宫信息 从题意和样例数据可以看出，迷宫中每个方格的行下标和列下标，都是从1开始编号的。 为了便于处理，我们也可以将数组预留一部分空间，数组行下标和列下标也从1开始编号l mapij取值为0，表示可以通过；取值为1，表示有障碍，不可通过l 因为数组的行下标和列下标都从1开始，且1=N、M(1, 2)-(1, 1).的重复递归调用，导致程序死循环，函数无法退出00001010063、迷宫求解、迷宫求解-定义数组标记方格已经被访问（定义数组标记方格已经被访问（解决死循环解决

2、死循环）7练习练习8洛谷洛谷P1238(走迷宫、求迷宫的所有路径走迷宫、求迷宫的所有路径)91、洛谷、洛谷P1238(走迷宫、求迷宫的所有路径走迷宫、求迷宫的所有路径)-解题思路解题思路该题的解题思路与上题类似以起始点为参照，寻找上、下、左、右可到达的方格将上、下、左、右可到达的方格设为新的起始点1.回到步骤1。直到没有可到达的方格或者到达终点为止100011101011101101110111110DFS搜索树与回溯搜索树与回溯 有一棵如右图的路径树，假设我们寻找一条从小红点到小绿点的路径 在寻找路径时，若遇到不满足条件的组合，往回走的过程，就称之为回溯112、洛谷、洛谷P1238(走迷宫走

3、迷宫)-编写程序判断是否存在从起点到达终点编写程序判断是否存在从起点到达终点的路径的路径visit数组防止重复递归123、洛谷、洛谷P1238(走迷宫走迷宫)-定义数组，保存求解路径定义数组，保存求解路径每条路径最多经过所有的方格134、洛谷、洛谷P1238(走迷宫走迷宫)-增加路径展示函数增加路径展示函数145、洛谷、洛谷P1238(走迷宫走迷宫)-重置访问状态，实现寻找过程回溯重置访问状态，实现寻找过程回溯将visit置0，实现路径寻找回溯15洛谷洛谷P1141(01迷宫迷宫)题目意思：求从某一格开始可到达的格子总数161、洛谷、洛谷P1141(01迷宫迷宫)-寻找递推过程寻找递推过程以左

4、边的迷宫为例，假如从第2行、第3列出发（行和列从1开始编号）令：lAi, j为迷宫第i行、第j列的数字，则Ai, j的取值为0或者1lTi, j为从第i行、第j列出发可到达的格子总数，则从第2行第3列出发，可到达的格子总数可记为T2, 3求解递推过程如下（因为可到达的格子总数包含自身所以要加1）：l因为A2, 3 = 0，所以：T2, 3 = T2, 2 + T2, 4 + T3, 3 + 1l因为A2, 2 = 1，所以：T2, 2 = T1, 2 + 1l因为A2, 4 = 0，所以：T2, 4 = T1, 4 + T2, 5 + T4, 3 + 1l因为A3, 3 = 0，所以：T3,

5、3 = T3, 4 + 1l重复如上递推步骤，直到某个格子不可到达相邻的任何格子为止1000110110101001101001000100011001100011100110001172、洛谷、洛谷P1141(01迷宫迷宫)-定义数据结构读取迷宫信息定义数据结构读取迷宫信息因为输入共有n行，每行n个字符，字符的取值只有0或1，字符间无空格。所以我们可以定义二维字符数组来保存迷宫的信息，同时以读入字符串的方式读取迷宫信息。由于字符串需要额外的空间保存结束符0，且n (1, 2)-(1, 1)-(1, 2)-(1, 1).重复的递归调用，无法结束。直至消耗完所有的栈内存，导致程序运行崩溃。100

6、010101203、洛谷、洛谷P1141(01迷宫迷宫)-防止程序死循环崩溃（防止程序死循环崩溃（解决办法解决办法）我们可以按如下方式，防止重复的递归调用。定义二维数组标记方格是否已经被访问1.在递归过程中过滤掉已经访问过的方格214、洛谷、洛谷P1141(01迷宫迷宫)-优化运算时间优化运算时间到此为止，虽然我们能求出所有方格可到达的方格数，但是如果需要求解的起点数量m太大时，就会超时。通过分析可以发现每个格子可以到达的格子数量有如下特点：l从某个格子出发，在求解过程中所经过的所有格子，它们可到达的格子总数都相同。l假如从(2, 3)出发，可到达(2, 2)、(2, 4)、(3, 3)、(1

7、, 2)、(1, 4)、(2, 5)、(4, 3)、(3, 4).； 那么T2, 3 = T2, 2 = T2, 4 = T3, 3 = T1, 2 = T1, 4. 基于该特点，我们可以采用如下方式优化程序的运行时间定义数组int P1000*10002，记录从指定方格出发，可到达的所有方格的行下标和列下标。定义数组int R10001000，保存从每个方格出发，可到达的方格数量。若从(x, y)出发可达到的方格数为A，则求解过程中经过的所有方格，它们可到达的方格数都为A。针对输入的x, y，若Rxy 0 则可直接输出结果，无需再次计算，节约计算时间224、洛谷、洛谷P1141(01迷宫迷宫)-优化运算时间优化运算时间23洛谷洛谷P3956(棋盘棋盘)-NOIP2017PJT3241、洛谷、洛谷P3956(棋盘棋盘)-编写路径递推搜索模板编写路径递推搜索模板252、洛谷、洛谷P3956(棋盘棋盘)-统计路径中花费的金币，计算花费的最少统计路径中花费的金币，计算花费的最少金币金币求所有路径中的最小花费从一个棋格到另一个棋格需要花费的金币263、洛谷、洛谷P3956(棋盘棋盘)-记录路径中棋格的颜色，完善魔法的限制记录路径中棋格的颜色，完善魔法的限制功能功能经过的