当前位置: 首页 > news >正文

C++ 迷宫问题

描述

定义一个二维数组 N*M ,如 5 × 5 数组下所示:


int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};


它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围: 2≤𝑛,𝑚≤10 2≤n,m≤10  , 输入的内容只包含 0≤𝑣𝑎𝑙≤1 0≤val≤1 

输入描述:

输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。

输出描述:

左上角到右下角的最短路径,格式如样例所示。

示例1

输入:

5 5
0 1 0 0 0
0 1 1 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)
#include <iostream>
#include <utility>
#include <variant>
#include <vector>
using namespace std;constexpr int N = 10;int n, m;
int maze[N][N] = {0};
int vist[N][N] = {0};std::vector<std::pair<int, int>> path;
std::vector<std::pair<int, int>> temp;void dfs(int x, int y)
{if(x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == 1 || vist[x][y] == 1){return;}vist[x][y] = 1;temp.emplace_back(x, y);//如果走到出口,则保存走过的路径if(x == n -1 && y == m - 1){path = temp;}//前后左右试探dfs(x, y+1); dfs(x+1,y);dfs(x-1,y);dfs(x, y-1);vist[x][y] = 0;temp.pop_back();
}int main() {cin >> n;cin >> m;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> maze[i][j];}}dfs(0,0);for(auto p : path){std::cout << "(" << p.first << "," << p.second <<")" << "\n"; }
}
// 64 位输出请用 printf("%lld")

http://www.lryc.cn/news/376879.html

相关文章:

  • 【Linux】Linux文件系统中主要文件夹列举_作用说明
  • 移植案例与原理 - HDF驱动框架-驱动配置(1)
  • 坚持刷题|反转链表
  • 升级和维护老旧LabVIEW程序
  • sqlite数据库整体迁移进mysql整个流程并解决中文异常问题
  • Hadoop3:MapReduce中的Partition原理及自定义Partition
  • 就因为没在大屏项目加全屏按钮,早上在地铁挨了领导一顿骂
  • STM32学习记录(八)————定时器输出PWM及舵机的控制
  • Vue CLI,Vue Router,Vuex
  • 互联网广告相关概念
  • 如何在服务器上部署一个java程序
  • 白酒:中国的酒文化的传承与发扬
  • 算法金 | 再见!!!梯度下降(多图)
  • python Django安装及怎么检测是否安装成功
  • Swift开发——存储属性与计算属性
  • 如何解决input输入时存在浏览器缓存问题?
  • Java基础学习-方法
  • Ribbon与Nginx的区别
  • R包开发详细教程
  • 图像的高频和低频细节
  • PostgreSQL源码分析——常量表达式化简
  • 速卖通自养号测评:安全高效的推广手段
  • 项目监督与控制
  • 【LeetCode刷题】面试题 17.19. 消失的两个数字
  • 如何定制Spring的错误json信息
  • 【第20章】Vue实战篇之Vue Router(路由)
  • 阿里云运维第一步(监控):开箱即用的监控
  • Python量化交易学习——Part7:定制增强型中证红利策略
  • 拥抱未来:探索改变游戏规则的新存储技术
  • shell中的流程控制