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

递归与深度优先搜索迷宫求解1、迷宫求解--定义数据结构，读取迷宫信息•从题意和样例数据可以看出，迷宫中每个方格的行下标和列下标，都是从1开始编号的。•为了便于处理，我们也可以将数组预留一部分空间，数组行下标和列下标也从1开始编号map[i][j]取值为0，表示可以通过；取值为1，表示有障碍，不可通过因为数组的行下标和列下标都从1开始，且1=N、M=5；所以行数和列数都应为62、迷宫求解-解题思路1.以起点为参照，寻找上、下、左、右可到达的方格(没有障碍)2.分别以上、下、左、右可到达的方格为新的起点。回到步骤1。直到没有可到达的方格或到达终点为止0000101010010011101101000走到终点递归寻找路径3、迷宫求解-定义数组标记方格已被访问过为了防止重复递归调用，导致运行出错。我们需要定义一个数组标记方格是否已经被访问过。我们以右边的迷宫为例进行说明。•假设从方格(1,1)到达方格(3,3)•当以方格(1,1)为参照时，它可以到达的方格有(1,2)、(2,1)•当以方格(1,2)为参照时，它可以到达的方格有方格(1,1)、(1,3)•依此类推，就会形成(1,1)--(1,2)--(1,1)...的重复递归调用，导致程序死循环，函数无法退出0000101003、迷宫求解-定义数组标记方格已经被访问（解决死循环）练习洛谷P1238(走迷宫、求迷宫的所有路径)1、洛谷P1238(走迷宫、求迷宫的所有路径)--解题思路该题的解题思路与上题类似1.以起始点为参照，寻找上、下、左、右可到达的方格2.将上、下、左、右可到达的方格设为新的起始点3.回到步骤1。直到没有可到达的方格或者到达终点为止1000111010111011011101111DFS搜索树与回溯•有一棵如右图的路径树，假设我们寻找一条从小红点到小绿点的路径•在寻找路径时，若遇到不满足条件的组合，往回走的过程，就称之为回溯2、洛谷P1238(走迷宫)--编写程序判断是否存在从起点到达终点的路径visit数组防止重复递归3、洛谷P1238(走迷宫)--定义数组，保存求解路径每条路径最多经过所有的方格4、洛谷P1238(走迷宫)--增加路径展示函数5、洛谷P1238(走迷宫)--重置访问状态，实现寻找过程回溯将visit置0，实现路径寻找回溯洛谷P1141(01迷宫)题目意思：求从某一格开始可到达的格子总数1、洛谷P1141(01迷宫)--寻找递推过程1.以左边的迷宫为例，假如从第2行、第3列出发（行和列从1开始编号）令：A[i,j]为迷宫第i行、第j列的数字，则A[i,j]的取值为0或者1T[i,j]为从第i行、第j列出发可到达的格子总数，则从第2行第3列出发，可到达的格子总数可记为T[2,3]2.求解递推过程如下（因为可到达的格子总数包含自身所以要加1）：因为A[2,3]==0，所以：T[2,3]=T[2,2]+T[2,4]+T[3,3]+1因为A[2,2]==1，所以：T[2,2]=T[1,2]+1因为A[2,4]==0，所以：T[2,4]=T[1,4]+T[2,5]+T[4,3]+1因为A[3,3]==0，所以：T[3,3]=T[3,4]+1重复如上递推步骤，直到某个格子不可到达相邻的任何格子为止10001101101010011010010001000110011000111001100012、洛谷P1141(01迷宫)--定义数据结构读取迷宫信息1.因为输入共有n行，每行n个字符，字符的取值只有0或1，字符间无空格。所以我们可以定义二维字符数组来保存迷宫的信息，同时以读入字符串的方式读取迷宫信息。2.由于字符串需要额外的空间保存结束符'\0'，且n=1000；因此迷宫的定义和迷宫信息的读取代码如下：2、洛谷P1141(01迷宫)--定义函数实现递推过程1.以当前方格为参照，寻找上、下、左、右可到达的方格2.以上、下、左、右可到达的方格为参照，重复步骤1。直到没有可到达的方格为止10001110100110110001011003、洛谷P1141(01迷宫)--防止程序死循环崩溃（错误分析）按前面的思路编写好代码后，我们发现程序虽然能运行，但运行一段时间后就会崩溃，为什么会崩溃呢？我们以左边的迷宫为例来进行说明。1.假设我们从方格(1,1)出发，那么它可到达的方格有(1,2)、(2,1)2.我们继续以方格(1,2)为参照，那么它可达到的方格有(1,1)、(2,2)3.接下来会再次以方格(1,1)为参照，重复步骤1、2。4.基于如上分析，程序会一直(1,1)-(1,2)-(1,1)-(1,2)-(1,1).....重复的递归调用，无法结束。直至消耗完所有的栈内存，导致程序运行崩溃。1000101013、洛谷P1141(01迷宫)--防止程序死循环崩溃（解决办法）我们可以按如下方式，防止重复的递归调用。1.定义二维数组标记方格是否已经被访问2.在递归过程中过滤掉已经访问过的方格4、洛谷P1141(01迷宫)--优化运算时间1.到此为止，虽然我们能求出所有方格可到达的方格数，但是如果需要求解的起点数量m太大时，就会超时。通过分析可以发现每个格子可以到达的格子数量有如下特点：从某个格子出发，在求解过程中所经过的所有格子，它们可到达的格子总数都相同。假如从(2,3)出发，可到达(2,2)、(2,4)、(3,3)、(1,2)、(1,4)、(2,5)、(4,3)、(3,4).......；那么T[2,3]==T[2,2]==T[2,4]==T[3,3]==T[1,2]==T[1,4].......2.基于该特点，我们可以采用如下方式优化程序的运行时间1.定义数组intP[1000*1000][2]，记录从指定方格出发，可到达的所有方格的行下标和列下标。2.定义数组intR[1000][1000]，保存从每个方格出发，可到达的方格数量。若从(x,y)出发可达到的方格数为A，则求解过程中经过的所有方格，它们可到达的方格数都为A。3.针对输入的x,y，若R[x][y]0则可直接输出结果，无需再次计算，节约计算时间4、洛谷P1141(01迷宫)--优化运算时间洛谷P3956(棋盘)--NOIP2017PJT31、洛谷P3956(棋盘)-编写路径递推搜索模板2、洛谷P3956(棋盘)-统计路径中花费的金币，计算花费的最少金币求所有路径中的最小花费从一个棋格到另一个棋格需要花费的金币3、洛谷P3956(棋盘)-记录路径中棋格的颜色，完善魔法的限制功能经过的路径上原来棋格的颜色4、洛谷P3956(棋盘)-搜索减枝，初步减少搜索时间5、洛谷P3956(棋盘)-添加最小基本记忆数组，再次减少搜索时间谢谢观赏!知识回顾KnowledgeReview