AcWing 844. 走迷宫
原题链接
简单
作者:
1025_xp
,
2022-12-12 23:25:14
,
所有人可见
,
阅读 126
模板:(走迷宫)
自己写了个DFS哈哈哈~ (20数据量就炸了T_T)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int g[N][N],d[N][N];
int n,m,sum=1e9+7; //sum记录最短路步数
int s[2][4]={ //增广数组遍历坐标
0,0,1,-1,
1,-1,0,0
};
bool check(int x,int y) //检查函数check();
{
if(x<0||x>=n||y<0||y>=m)
return false;
if(g[x][y]==1||d[x][y]==1)
return false;
return true;
}
void dfs(int x,int y,int ans)
{
if(x==n-1&&y==m-1){ //到终点就更新sum
sum=min(sum,ans);
return;
}
for(int i=0;i<4;i++){ //检查四个坐标
int x_n=x+s[0][i];
int y_n=y+s[1][i];
if(check(x_n,y_n)){
d[x_n][y_n]=1;
dfs(x_n,y_n,ans+1);
d[x_n][y_n]=0;
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++){ //输入模块
for(int j=0;j<m;j++){
cin>>g[i][j];
}
}
dfs(0,0,0); //x,y,ans;ans为记录步数
printf("%d",sum);
return 0;
}