回溯 DFS——连通性和搜索顺序 _dfs

文章目录搜索顺序(回溯) 总结
概述定义
在深度优先搜索中，对于最新发现的顶点，如果它还有以此为顶点而未探测到的边，就沿此边继续探测下去，当顶点v的所有边都已被探寻过后，搜索将回溯到发现顶点v有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点为止。如果还存在未被发现的顶点，则选择其中一个作为源顶点，并重复上述过程。整个过程反复进行，直到所有的顶点都被发现时为止。分类
【回溯DFS——连通性和搜索顺序】内部dfs：一般为连通性问题，整个图作为一个状态。只需要把图中每个点都遍历到，记录其存在或者一些性质的状态即可。
外部dfs：一般求方案数量和最值，搜索顺序的不同状态也不同，应带有回溯。
连通性问题模板
def dfs(u) :if (障碍终止条件\优化终止条件) : return ..if (终点终止条件) : return ..st[u] = True #标记已经遍历过for i in range(...) : #选择路径t = u + path[i]if 边界条件 : continueif st[t] : continuedfs(t)
思考
连通性问题实质上是存在性问题，一般可以求解是否存在连通块与存在连通块的个数
迷宫
一天在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n?n 的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。
同时当处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，想要从点A走到点B，问在不走出迷宫的情况下能不能办到。
如果起点或者终点有一个不能通行(为#)，则看成无法办到。
注意：A、B不一定是两个不同的点。
输入格式
第1行是测试数据的组数 k，后面跟着 k 组输入。
每组测试数据的第1行是一个正整数 n，表示迷宫的规模是 n?n 的。
接下来是一个 n?n 的矩阵，矩阵中的元素为.或者# 。
再接下来一行是 4 个整数 ha,la,hb,lb，描述 A 处在第 ha 行, 第 la 列，B 处在第 hb 行, 第 lb 列。
注意到 ha,la,hb,lb 全部是从 0 开始计数的。
输出格式
k行，每行输出对应一个输入。
能办到则输出“YES”，否则输出“NO” 。
数据范围
1≤n≤100
输入样例：
.##
…#
#…
0 0 2 2
…
###.#
…#…
###…
…#.
0 0 4 0
输出样例:
YES
NO
import syssys.setrecursionlimit(110 * 110)T = int(input())DIRC = [[-1, 0], [0, 1], [1, 0], [0, -1]]def dfs(sx, sy, ex, ey) :if g[sx][sy] == '#' :#障碍终止条件return Falseif sx == ex and sy == ey : return True #终点终止条件st[sx][sy] = True #标记状态for i in range(4) : #遍历路径a, b = sx + DIRC[i][0], sy + DIRC[i][1]if a < 0 or a >= n or b < 0 or b >= n : continue # 越界筛查if st[a][b] : continue #去重if dfs(a, b, ex, ey) : return True #存在通路则返回Truereturn False #没有通路返回Falsefor t in range(T) :n = int(input())g = []for i in range(n) :g.append(input())sx, sy, ex, ey = map(int, input().split())st = [[False] * n for _ in range(n)]if dfs(sx, sy, ex, ey) : print("YES")else : print("NO")
红与黑
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。
请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
输入格式
输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。