DFS题解

提示：
数据结构选择
首先我们需要选择合适的数据结构来表示这个迷宫。最直观的选择就是使用一个二维数组，比如a[n][m]，其中a[i][j]表示第i行第j列的格子状态。

算法选择
为了找到一条从起点到终点的路径，我们可以考虑使用深度优先搜索(DFS)或广度优先搜索(BFS)算法。这两种算法都可以用来遍历图中的节点，寻找是否存在一条从起点到终点的路径。本题解围深度优先搜索（DFS）

具体步骤
初始化: 创建一个二维数组a[n][m]，根据输入填充迷宫的状态。

DFS: 在递归过程中检查当前格子是否为终点。如果不是，则尝试访问四个方向（上、下、左、右）的相邻格子，并确保这些格子没有被访问过且不是障碍物。

如果在搜索过程中到达了终点，则输出YES。
如果搜索结束后仍未到达终点，则输出NO。
实现细节
在搜索过程中需要特别注意边界条件，即不要访问迷宫外的格子。
对于DFS，要注意递归的终止条件。
我们可以在原数组中修改，使得做过的路为障碍。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[51][51],t,bj[51][51];
int fx[5]={0,0,0,1,-1};
int fy[5]={0,1,-1,0,0};
void dfs(int x,int y){
a[x][y]=1;
if(xn&&ym){
cout<<"YES";
t=1;
return;
}for(int i=1;i<=4;i++){
int tx=x+fx[i];
int ty=y+fy[i];
if(a[tx][ty]0&&tx>0&&tx<=n&&ty<=m&&ty>0)dfs(tx,ty);
}a[x][y]=0;//此处注意要在回溯的时候将其改为可通行路段，以防从别处来的走不通
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}dfs(1,1);
if(t0)cout<<"NO";
return 0;
}