一、深度优先搜索

深度优先搜索（DFS）是一种用于图遍历或树遍历的算法。它的核心思想是尽可能地向深度方向遍历，直到到达最深处，然后返回上一个节点，继续向另一个方向遍历。

深度优先搜索的实现可以使用递归或栈（迭代版本）来实现。以下是递归实现的示例代码：

# 使用邻接列表表示图graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []}visited = set() # 用于记录已经访问过的节点def dfs(node):if node not in visited:print(node)visited.add(node)for neighbor in graph[node]:dfs(neighbor)dfs('A')

在这个示例中，dfs函数递归地遍历邻接列表表示的图。如果当前节点没有被访问过，则输出该节点，将其添加到已访问集合中，并递归访问其邻居节点。

下面是使用栈实现深度优先搜索的示例代码：

# 使用邻接列表表示图graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []}visited = set() # 用于记录已经访问过的节点def dfs(start):stack = [start]while stack:node = stack.pop()if node not in visited:print(node)visited.add(node)for neighbor in graph[node]:stack.append(neighbor)dfs('A')

在这个示例中，dfs函数使用栈来实现深度优先搜索。它从起始节点开始，将其入栈。然后进入一个循环，弹出栈顶节点，如果该节点没有被访问过，则输出该节点，将其添加到已访问集合中，并将其邻居节点压入栈中。循环继续，直到栈为空。

题目背景

给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

这是一个典型的搜索问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。由于题目中给定了障碍，所以在搜索过程中需要判断当前位置是否是障碍，如果是则不能继续搜索。

下面以DFS为例，给出一个可能的实现：

def dfs(x, y, visited, end_x, end_y, maze):if x == end_x and y == end_y:return 1visited[x][y] = Truecount = 0for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:new_x, new_y = x + dx, y + dyif 0 <= new_x < len(maze) and 0 <= new_y < len(maze[0]) and not visited[new_x][new_y] and not maze[new_x][new_y]:count += dfs(new_x, new_y, visited, end_x, end_y, maze)visited[x][y] = Falsereturn countdef num_paths(start_x, start_y, end_x, end_y, maze):visited = [[False]*len(maze[0]) for _ in range(len(maze))]return dfs(start_x, start_y, visited, end_x, end_y, maze)

其中，dfs函数表示从当前位置开始搜索，已经访问过的位置保存在visited中，终点坐标是(end_x, end_y)，maze表示整个迷宫。num_paths函数是最终的接口函数，用于调用dfs函数并返回结果。

需要注意的是，在搜索过程中，已经访问过的位置需要标记为已访问，避免重复搜索，但在返回时需要将其标记为未访问，以允许其他路径从该位置经过。另外，在搜索时需要判断当前位置是否越界或是障碍，避免出现数组下标越界或是走到障碍的情况。

二、广度优先搜索

广度优先搜索（Breadth-First Search，BFS）是一种基于图形数据结构的算法，用于解决从起点到目标节点的最短路径问题。BFS以图形结构为基础，逐层搜索与起点相邻的节点，并且保持搜索距离一层一层地增加，直到找到目标节点或者遍历完所有节点。

下面是广度优先搜索的实现步骤：

定义一个队列Q，并将起点节点放入队列中。将起点节点标记为已访问。从队列中弹出节点并检查该节点是否为目标节点，如果是，则结束搜索。如果不是目标节点，则将该节点的所有未访问过的相邻节点加入队列中，并标记它们为已访问。重复步骤3-4，直到找到目标节点或者遍历完所有节点。

BFS算法可以使用迭代或者递归的方式进行实现。以下是Python中使用队列实现BFS算法的非递归实现：

from collections import dequedef bfs(graph, start):visited = set() # 用集合来存储已访问过的节点queue = deque([start]) # 使用双向队列来存储待访问的节点visited.add(start) # 标记起始节点为已访问while queue:vertex = queue.popleft() # 取出队列中的第一个节点print(vertex, end=" ")for neighbor in graph[vertex]: # 遍历该节点的所有邻居节点if neighbor not in visited: # 如果邻居节点没有被访问过visited.add(neighbor) # 标记为已访问queue.append(neighbor) # 将邻居节点加入队列

其中，graph参数为图的邻接表表示，start参数为起始节点。在该实现中，使用了Python标准库中的deque类来实现队列的功能，同时使用了Python的set类来存储已访问的节点，以避免重复访问。bfs函数中的while循环用于不断地取出队列中的节点进行访问，直到队列为空为止。

递归方式实现BFS也是可行的。递归方式的BFS可以看作是一个深度优先搜索（DFS）的变种，它通过使用队列来保存每一层的节点，从而实现了广度优先的搜索方式。BFS算法通常使用非递归实现，但是在某些情况下也可以使用递归实现，例如对于较小的图。

以下是BFS算法的Python递归实现：

from collections import dequedef bfs(graph, queue, visited):if not queue:returnnode = queue.popleft()print(node)for neighbor in graph[node]:if neighbor not in visited:queue.append(neighbor)visited.add(neighbor)bfs(graph, queue, visited)# 以字典形式表示图graph = {'A': ['B', 'D'],'B': ['A', 'C', 'F'],'C': ['B', 'F'],'D': ['A', 'E'],'E': ['D', 'F'],'F': ['B', 'C', 'E'],}# 创建空队列和集合，并将起始节点加入队列和集合queue = deque(['A'])visited = set(['A'])# 调用递归函数bfs(graph, queue, visited)

在递归实现中，我们定义了一个名为bfs的递归函数，它接受三个参数：graph表示图的字典，queue表示当前要访问的节点队列，visited表示已访问过的节点集合。

首先，我们从队列中取出队首节点，并打印该节点的值。然后，我们遍历该节点的邻居节点，并将邻居节点添加到队列中，并将其标记为已访问。最后，我们递归调用bfs函数，以便继续遍历下一个节点。

在主程序中，我们首先创建空队列和集合，并将起始节点加入队列和集合。然后，我们调用bfs函数，以开始遍历整个图。

需要注意的是，递归方式实现BFS的性能通常不如迭代方式实现BFS。因为递归会产生函数调用的开销，而队列的操作也会导致额外的内存开销。因此，在实际应用中，通常建议使用迭代方式实现BFS。

题目：

有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步

题解：

这是一个典型的图论问题，可以使用广度优先搜索（BFS）来解决。

具体步骤如下：

创建一个二维数组dist，用来记录每个点到马所在点的最短距离。初始化为全零。将马所在点加入一个队列q中，同时将其dist值设为0。对队列进行广度优先搜索。从队列中取出一个点，将其周围可以到达的点加入队列，并更新这些点的dist值。注意，这里的“可以到达的点”是指棋盘上的合法位置，即横、纵坐标都在棋盘范围内，并且与当前点的横、纵坐标之差的绝对值之和为3。重复步骤3，直到队列为空。

最后，dist数组中记录的就是每个点到马所在点的最短距离。

以下是Python代码实现：

from collections import dequedef min_steps(n, m, x, y):# 初始化dist数组dist = [[0] * m for _ in range(n)]# 将马所在点加入队列并标记dist值为0q = deque([(x, y)])dist[x][y] = 0# 广度优先搜索while q:cur_x, cur_y = q.popleft()for dx, dy in [(1, 2), (2, 1), (1, -2), (2, -1), (-1, 2), (-2, 1), (-1, -2), (-2, -1)]:next_x, next_y = cur_x + dx, cur_y + dyif 0 <= next_x < n and 0 <= next_y < m and dist[next_x][next_y] == 0:dist[next_x][next_y] = dist[cur_x][cur_y] + 1q.append((next_x, next_y))return dist

这个函数的输入参数为棋盘的行数n、列数m以及马所在点的横、纵坐标x、y。输出为一个二维数组，记录了每个点到马所在点的最短距离。