搬家网站模板,松江洞泾网站建设,element ui做的网站,晋江友情链接是什么意思文章目录 思路：DFSBFSBFS和DFS的特点BFS 与 DFS 的区别BFS 的优点BFS 时间复杂度深度优先搜索（DFS）的优点深度优先搜索（DFS）的时间复杂度解释：空间复杂度总结：例如下面的迷宫：
// 迷宫的表示：0表示可以走，1表示障碍
vectorvectorint maze = {{0, 0,… 文章目录 思路：DFSBFS BFS和DFS的特点BFS 与 DFS 的区别BFS 的优点BFS 时间复杂度深度优先搜索（DFS）的优点深度优先搜索（DFS）的时间复杂度解释：空间复杂度总结： 例如下面的迷宫：
// 迷宫的表示：0表示可以走，1表示障碍
vectorvectorint maze = {{0, 0, 1, 0, 0},{1, 0, 1, 1, 0},{1, 0, 0, 1, 0},{0, 0, 0, 0, 0},{1, 1, 1, 1, 0}
};要实现解决迷宫的问题，可以使用回溯法深度优先搜索(DFS）或者广度优先搜索（BFS）。
思路：
迷宫中的 0 表示可走的路，1 表示障碍。 起点是 (0, 0)，终点是 (n-1, m-1)。 可以向上、下、左、右四个方向移动。 通过回溯法探索每个可能的路径，当找到终点时，返回路径。
下面分别使用DFS和BFS来实现。
DFS
/*深度搜索 dfs*/#include iostream
#include vectorusing namespace std;// 定义行的上下左右四个方向的移动
// -1表示向上移动，1表示向下移动，0表示不改变行
int row_dir[] = { -1, 1, 0, 0 }; // 定义行的上下左右四个方向的移动
// -1表示向左移动，1表示向右移动，0表示不改变列
int col_dir[] = { 0, 0, -1, 1 };// 检查当前位置是否有效，且未被访问过
bool isValid(int x, int y, const vectorvectorint maze, vectorvectorbool visited)
{return (x = 0 x maze.size() y = 0 y maze[0].size() maze[x][y] == 0 !visited[x][y]);
}// 回溯法解决迷宫问题
bool solveMaze(int x, int y, const vectorvectorint maze, vectorvectorbool visited, vectorpairint, int path)
{// 到达终点if (x == maze.size()
