全国青少年信息学奥林匹克竞赛NOI信息学递归与深度优先搜索DFS课件

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

2、类似以起始点为参照，寻找上、下、左、右可到达的方格将上、下、左、右可到达的方格设为新的起始点回到步骤1。直到没有可到达的方格或者到达终点为止1000111010111011011101111DFS搜索树与回溯有一棵如右图的路径树，假设我们寻找一条从小红点到小绿点的路径在寻找路径时，若遇到不满足条件的组合，往回走的过程，就称之为回溯2、洛谷P1238(走迷宫)-编写程序判断是否存在从起点到达终点的路径visit数组防止重复递归3、洛谷P1238(走迷宫)-定义数组，保存求解路径每条路径最多经过所有的方格4、洛谷P1238(走迷宫)-增加路径展示函数5、洛谷P1238(走迷宫)-重置访问状态，实现

3、寻找过程回溯将visit置0，实现路径寻找回溯洛谷P1141(01迷宫)题目意思：求从某一格开始可到达的格子总数1、洛谷P1141(01迷宫)-寻找递推过程以左边的迷宫为例，假如从第2行、第3列出发（行和列从1开始编号）令：Ai, j为迷宫第i行、第j列的数字，则Ai, j的取值为0或者1Ti, j为从第i行、第j列出发可到达的格子总数，则从第2行第3列出发，可到达的格子总数可记为T2, 3求解递推过程如下（因为可到达的格子总数包含自身所以要加1）：因为A2, 3 = 0，所以：T2, 3 = T2, 2 + T2, 4 + T3, 3 + 1因为A2, 2 = 1，所以：T2, 2 = T1

4、, 2 + 1因为A2, 4 = 0，所以：T2, 4 = T1, 4 + T2, 5 + T4, 3 + 1因为A3, 3 = 0，所以：T3, 3 = T3, 4 + 1重复如上递推步骤，直到某个格子不可到达相邻的任何格子为止10001101101010011010010001000110011000111001100012、洛谷P1141(01迷宫)-定义数据结构读取迷宫信息因为输入共有n行，每行n个字符，字符的取值只有0或1，字符间无空格。所以我们可以定义二维字符数组来保存迷宫的信息，同时以读入字符串的方式读取迷宫信息。由于字符串需要额外的空间保存结束符0，且n (1, 2)-(1,

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

6、(2, 4)、(3, 3)、(1, 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 则可直接输出结果，无需再次计算，节约计算时间4、洛谷P1141(01迷宫)-优化运算时间洛谷P3956(棋盘)-NOIP2017PJT31、洛谷P3956(棋盘)-编写路径递推搜索模板2、洛谷P3956(棋盘)-统计路径中花费的金币，计算花费的最少金币求所有路径中的最小花费从一个棋格到另一个棋格需要花费的金币3、洛谷P3956(