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

算法提高之迷宫问题

算法提高之迷宫问题

  • 核心思想:最短路问题

    • 从(n-1,n-1)开始bfs 往前走一个就存入pre数组 之后再遍历pre数组输出
  •   #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1010,M =N*N;#define x first#define y secondtypedef pair<int, int> PII;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};PII pre[N][N];int g[N][N];int n;bool st[N][N];int hh,tt=-1;PII p[M];void bfs(){st[n-1][n-1] = true;p[++tt] = {n-1,n-1};  //从n-1,n-1开始while(hh<=tt){PII t = p[hh++];int a=t.x,b=t.y;for(int i=0;i<4;i++){int x = a+dx[i],y = b+dy[i];if(x<0||x>=n||y<0||y>=n||g[x][y]||st[x][y]) continue;st[x][y] = true;p[++tt] = {x,y};pre[x][y] = t;  //x,y前驱为t(实际是后驱吧 t -> (x,y))}}int x=0,y=0;  //正序输出while(x!=n-1 || y!=n-1){cout<<x<<" "<<y<<endl;auto t = pre[x][y];x = t.x,y = t.y;}cout<<n-1<<" "<<n-1<<endl;}int main(){cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)    cin>>g[i][j];bfs();return 0;}
    
http://www.lryc.cn/news/344745.html

相关文章:

  • 泛微E9开发 通过点击按钮来复制选择的明细行
  • sqlalchemy 分表实现方案
  • QML进阶(十五) QML各种标准元素的用法
  • 【工具使用】快速实现Makefile模板的方法
  • Linux-信号执行
  • 在线听歌播放器 梨花带雨网页音乐播放器 网页音乐在线听 源码
  • 免费生成证件照
  • 深入探索数据链路层:网络通信的基石
  • STM32使用L9110驱动电机自制小风扇
  • C语言——队列的实现
  • 15-LINUX--线程的创建与同步
  • 【退役之重学Java】如何解决消息持续积压等问题
  • Linux下的SPI通信
  • 【转载】数字化工厂规划蓝图报告
  • 《基于GNU-Radio和USRP的雷达通信系统的实现》文献阅读
  • Sealos急速部署生产用k8s集群
  • VTK数据的读写--Vtk学习记录1--《VTK图形图像开发进阶》
  • Vue3专栏项目 -- 一、第一个页面(下)
  • 一栈走天下:使用HBuilderX高效搭建Uni-App微信小程序开发环境
  • docker安装Debian:11 freeswitch1.10.5
  • c3 笔记6 认识css样式表
  • 基于springboot+mybatis+vue的项目实战之增删改查CRUD
  • 字节跳动(社招)四面算法原题
  • 车道线检测交通信号识别车辆实时检测
  • 用正则表达式打造免费代理IP池
  • 【每日刷题】Day35
  • Python数据清洗与可视化实践:国际旅游收入数据分析
  • 前置知识储备
  • 六月品牌互动营销方案的作用是什么
  • dummy_worker C++ 预占用部分比例cpu资源,人为创造cpu资源紧张