原创 2024年1月23日15:32分提交, AC的同时内存和时间消耗超过100%用户

这个问题是典型的图论中的路径搜索问题，非常适合使用广度优先搜索（Breadth-First Search，简称BFS）或深度优先搜索（Depth-First Search，简称DFS）算法来解决。让我们一步步来分析如何解决这个问题： 1. 题目理解 首先，确保你完全理解了题目要求。我们有一个n×m的迷宫，其中某些位置是障碍物，某些位置是空地。起点和终点都是空地，你需要判断是否存在一条从起点到终点的路径，这条路径只能经过空地。 2. 数据结构选择 在解决这类问题时，我们需要一种数据结构来表示迷宫的状态。通常，二维数组是一个很好的选择，可以用它来存储迷宫的布局。例如，你可以定义一个二维数组maze[n][m]，其中maze[i][j]为'.'表示该位置是空地，为'#'表示该位置有障碍物。 3. 算法选择 对于这类问题，BFS和DFS都是可行的选择。BFS保证找到最短路径，而DFS可能更快但不一定能找到最短路径。在这个问题中，由于只需要判断是否可达，使用任一算法均可。下面以BFS为例进行讲解： BFS实现步骤： 初始化：创建一个队列Q用于存放待访问的位置，并将起点A(sx, sy)入队。同时，创建一个二维数组visited[n][m]，用于记录每个位置是否被访问过，初始时全部标记为未访问。 循环直到队列为空： 出队一个位置(x, y)。 如果这个位置是终点B(fx, fy)，则可以直接返回YES，因为找到了一条路径。 否则，检查该位置的上、下、左、右四个相邻位置是否在迷宫内且没有障碍物且没有被访问过。如果是，则将这些位置标记为已访问，并将它们加入队列Q中。 结束条件：如果队列Q为空时仍未找到路径至终点，返回NO。 4. 编程实践 开始编写代码前，先在纸上或白板上模拟几遍算法流程，确保你理解了每个步骤。然后，逐步将算法转换成代码，注意边界条件的处理，比如越界检测等。 5. 调试与测试 编写完代码后，不要急于提交。先自己构造一些测试用例，包括边界情况和极端情况，手动验证程序的正确性。使用题目给出的样例数据进行测试，确认输出结果符合预期。 6. 总结与反思 无论最终是否解决了问题，都应该对解题过程进行总结，思考是否有更优的解法或者在编码过程中有哪些可以改进的地方。

话不多说，正文开始!

为什么前面都有差不多的题了还有人不会做

A7991.迷宫 DFS题解 这是一道经典的深搜（深度优先搜索，DFS）模板题（虽然我用了AC助手才AC的）。 1. 思路： > 1、从 起点 开始，判断每个点是否符合题目条件 > 2、若符合条件，则从该点开始，向四周 搜索 > 3、若无法继续前进，则 返回 > 4、若可以前进，则 前进（通过 递归 实现） > 5、若到达终点，则给出相应答案并 结束 > 6、若无法到达终点，则给出相应答案并 退出 2. 完整代码：

#include <bits/stdc++.h> using namespace std; int n,m,sx,sy,fx,fy; char a[50][50];//地图 int vis[50][50];//标记数组 判断是否走过 int dir[4][2] = {1,0,0,1,-1,0,0,-1};//方向数组 bool f = 0;//f是标记 0表示不通 1表示可以走通 bool check(int x,int y){//判断是否越界 return x>=1 && x<=n && y>=1 && y<=m; } void dfs(int x,int y){ if(xfx && yfy){//走到右下角，结束 f = 1; return ; } for(int i=0;i<4;i++){//四个方向依次寻找 int nx = x + dir[i][0]; int ny = y + dir[i][1]; if(check(nx,ny) && a[nx][ny] != '#' && vis[nx][ny] == 0){ //未越界 && 可以走 && 未走过 vis[nx][ny] = 1; dfs(nx,ny); vis[nx][ny] = 0; } } } int main(){ cin>>n>>m; cin>>sx>>sy>>fx>>fy; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } vis[1][1] = 1; dfs(sx,sy); if(f == 1) cout<<"YES"; else cout<<"NO"; return 0; }