怎么制作网站弹出广告,百度快速seo优化,网站开发敬请期待,中小企业网络设计论文题目描述如下#xff1a; dfs算法解决迷宫问题的一个标准模板 #xff0c;通过递归与回溯暴力遍历所有能走的点#xff0c;并比较找出所有可行方案的最优解
解决这道问题的核心思想和组合数如出一辙#xff0c;可以说是组合数的升级版
结合注释看dfs更清晰易懂#xff0…题目描述如下 dfs算法解决迷宫问题的一个标准模板 通过递归与回溯暴力遍历所有能走的点并比较找出所有可行方案的最优解
解决这道问题的核心思想和组合数如出一辙可以说是组合数的升级版
结合注释看dfs更清晰易懂这里不再空对空的讲述了
本题要用bfs写dfs会超时但dfs找路径的核心思想是很值得学习的而且dfs比bfs的代码更简洁更好理解打oi赛制是可以得到部分分的
能过样例的代码如下
#include bits/stdc.h
using namespace std;
const int N110;
int a[N][N];
bool check[N][N];//记录该位置是否走过保证一个方案内不回头
int mi1e8;//最小步数,初始化为无穷大
void dfs(int stx,int sty,int step){//stx-start x,sty-start yint next[4][2]{{1,0},{0,-1},{-1,0},{0,1}};//下一步分别走右下左上的方案int nx,ny;//将要走到下一个位置的的坐标if(stxnstym) {//判断是否走到目标位置 if(stepmi){//更新最小步数 mistep;}return;}for(int k0;k4;k){//计算下一个点坐标 nxstxnext[k][0];nystynext[k][1];//判断是否越界,若越界直接continue重新走下一个方向不往下递归走出下一步 if (nx1||nxn||ny1||nym){continue;} //判断下一个点走过没有判断下一个点是否为障碍物若不是则递归走出下一步 if(check[nx][ny]falsea[nx][ny]0){check[nx][ny]true;//标记为走过和组合数的模板一样 dfs(nx,ny,step1);check[nx][ny]false;//回溯的过程这一步不走了把卡片拿回来 }}
}
int main(){int n,m;cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];}}check[1][1]true;//标记起点坐标已走过 dfs(1,1,0);//传入起点坐标和此时的步数0 coutmi;return 0;
}
