end深搜
2024-07-17 16:15:17
发布于:广东
#include <bits/stdc++.h>
using namespace std;
const int dirs[][2]={0,1,1,0,0,-1,-1,0};
const int INF=100;
int n,m;
vector<string>mat;
//从x,y出发到终点的最小步数
int dfs(int x,int y)
{
if(x==n-1 and y==m-1){
return 0;
}
mat[x][y]='#';//当前路径标记(x,y)为已经访问过
int step=INF;
for(int i=0;i<4;++i)
{
int nx=x+dirs[i][0];
int ny=y+dirs[i][1];
if(nx<0 or nx>=n or ny<0 or ny>=m) continue;
if(mat[nx][ny]=='#') continue;
step=min(step,dfs(nx,ny)+1);
}
mat[x][y]='.';//当前路径搜索完毕,取消(x,y)的标记
return step;
}
int main()
{
cin>>n>>m;
mat=vector<string>(n);
for(int i=0;i<n;++i)
{
cin>>mat[i];
}
int res=dfs(0,0);
if(res<INF) cout<<res;
else cout<<"-1";
return 0;
}
这里空空如也
有帮助,赞一个