深度优先搜索模板
2024-08-07 18:57:57
发布于:上海
#include<iostream>
using namespace std;
int n,m;
int mp[45][45];
int ans=30;
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int vis[45][45];
bool inmap(int x,int y){
return x>=1&&x<=n&&y>=1&&y<=m;
}void dfs(int x,int y,int step){
if(x==n&&y==m){
ans=min(ans,step);
return ;
}for(int i=0;i<4;i++){
int nx=x+dir[i][0],ny=y+dir[i][1];
if(inmap(nx,ny)&&mp[nx][ny]!='#'&&vis[nx][ny]==0){
vis[nx][ny]=1;
dfs(nx,ny,step+1);
vis[nx][ny]=0;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
dfs(1,1,0);
if(ans==30)cout<<-1;
else cout<<ans;
return 0;
}
这里空空如也
有帮助,赞一个