小白的DFS算法学习历程（不定期更新） |
您所在的位置：网站首页 › cs61b的project3 › 小白的DFS算法学习历程（不定期更新） |
|
迷宫算法（基础）
定义一个二维数组： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 输入一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。 输出左上角到右下角的最短路径，格式如样例所示。 样例输入 复制 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 样例输出 复制 (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4) 参考代码（并非本题标准答案，但有重要参考价值）： //迷宫问题的dfs算法 默认以矩形左下角点建立xOy坐标系 #include using namespace std; int min_step=99999;//代表最小步数 int arr[100][100];//遍历数组，0代表不可遍历，1代表可遍历 int visit[100][100];//访问标记数组，0代表未访问，1代表已经访问 //深度有限搜索算法，作用是将min_step改成最合理的最短路径值 void dfs(int a,int b,int p,int q,int step){ if(a==p&&b==q)//对应找到终点的一条路径，如果成功找到的情况 { if(step>m>>n;//构造出迷宫函数的行与列 for(int i=0;iarr[i][j]; } } int start_x,start_y,final_x,final_y;//初始值与终点值 cin>>start_x>>start_y>>final_x>>final_y; dfs(start_x,start_y,final_x,final_y,0); cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |