编程算法 - 迷宫的最短路径 代码(C++)
2023-09-11 14:20:56 时间
迷宫的最短路径 代码(C++)
本文地址: http://blog.csdn.net/caroline_wendy
题目: 给定一个大小为N*M的迷宫. 迷宫由通道和墙壁组成, 每一步能够向邻接的上下左右四格的通道移动.
请求出从起点到终点所需的最小步数. 请注意, 本题假定从起点一定能够移动到终点.
使用宽度优先搜索算法(DFS), 依次遍历迷宫的四个方向, 当有能够走且未走过的方向时, 移动而且步数加一.
时间复杂度取决于迷宫的状态数, O(4*M*N)=O(M*N).
代码:
/* * main.cpp * * Created on: 2014.7.17 * Author: spike */ /*eclipse cdt, gcc 4.8.1*/ #include <stdio.h> #include <limits.h> #include <utility> #include <queue> using namespace std; class Program { static const int MAX_N=20, MAX_M=20; const int INF = INT_MAX>>2; typedef pair<int, int> P; char maze[MAX_N][MAX_M+1] = { "#S######.#", "......#..#", ".#.##.##.#", ".#........", "##.##.####", "....#....#", ".#######.#", "....#.....", ".####.###.", "....#...G#" }; int N = 10, M = 10; int sx=0, sy=1; //起点坐标 int gx=9, gy=8; //重点坐标 int d[MAX_N][MAX_M]; int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; //四个方向移动的坐标 int bfs() { queue<P> que; for (int i=0; i<N; ++i) for (int j=0; j<M; ++j) d[i][j] = INF; que.push(P(sx, sy)); d[sx][sy] = 0; while (que.size()) { P p = que.front(); que.pop(); if (p.first == gx && p.second == gy) break; for (int i=0; i<4; i++) { int nx = p.first + dx[i], ny = p.second + dy[i]; if (0<=nx&&nx<N&&0<=ny&&ny<M&&maze[nx][ny]!='#'&&d[nx][ny]==INF) { que.push(P(nx,ny)); d[nx][ny]=d[p.first][p.second]+1; } } } return d[gx][gy]; } public: void solve() { int res = bfs(); printf("result = %d\n", res); } }; int main(void) { Program P; P.solve(); return 0; }
输出:
result = 22
相关文章
- C++BM算法
- C++ 算法大全
- 总结一些笔记上的C和C++知识点
- C++ 四种强制类型转换
- c++保存数据到TXT
- 基于c++、opencv、cuda、Visual Studio编程
- Open3D (C++) 等间距抽稀算法
- Paip.提升用户体验------在C++ Builder 不规则图片按钮实现总结
- Algorithm:C++语言实现之动态规划算法相关(矩阵连乘状态转移方程、字符串的交替连接、分析格网棋盘的特点、最短路线问题、生产计划问题、动态规划解下列非线性规划)
- Algorithm:C++语言实现之概率算法相关问题(计算机中的概率事件、C语言中的随机事件、产生二维随机数、圆内均匀取点)
- Algorithm:C++语言实现之贪心法算法相关问题
- Algorithm:C++语言实现之图论算法相关(图搜索广度优先BFS、深度优先DFS,最短路径SPF、带负权的最短路径Bellman-ford、拓扑排序)
- Algorithm:C++语言实现之内排序、外排序相关算法(插入排序 、锦标赛排序、归并排序)
- 环形链表(C++)
- Nim 游戏(C++)
- C/C++中指针和引用区别
- 【 华为OD机试 2023】最多颜色的车辆(C++ Java JavaScript Python)
- C++每日面试之字符串自定义解压算法
- C++ 二分法
- C++虚成员函数表vtable
- C++ this指针详解(精辟)
- C++11之thread用法(一百零七)
- VC++如何使用C++ STL标准模板库中的算法函数(附源码)
- 如何在VS C++中高亮用户自定义关键字
- 【初识C++】熟悉C++语言的语句、语法组成和基本编程方式,可以解决一般的算法问题
- 第k个数(c++, java)
- C++算法之巧解数学问题
- C++算法之二分查找
- C++、STL标准模板库和泛型编程 ——迭代器、 算法、仿函数(侯捷)
- 【C++】算法集锦(11):敏感词过滤算法(DFA)
- C++搭建集群聊天室(三):配置远程代码编辑神器 VScode
- 【强力推荐】基于Nvidia-Docker-Linux(Ubuntu18.04)平台:新版OpenCV5.x(C++)联合CUDA11.1(GPU)完美配置视觉算法开发环境
- 【维生素C语言】第十四章 - 浅析C/C++程序的内存开辟