UVA:1600 巡逻机器人
2024-10-06 07:01:33
机器人要从一个m*n(m和n的范围都在1到20的闭区间内)的网格的左上角(1,1)走到右下角(m,n)。网格中的一些格子是空地,用0表示,其它格子是障碍,用1表示。机器人每次可以往四个方向走一格,但不能连续地穿越k( [0,20] )个障碍,求最短路长度。起点和终点保证是空地。
思路:用bfs搜索即可,由于不能连续地穿越k个障碍,所以在原本的vis2维数组上面再添加1维,变成3维数组,表示穿越的墙的层数(障碍)。
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<queue>
- using namespace std;
- int n,m,k,t;
- int map[25][25];
- bool vis[25][25][25];//增加一个维度Z来表示跃过的墙的层数。
- int dx[4]= {1,0,-1,0};
- int dy[4]= {0,1,0,-1};
- struct Point
- {
- int x,y;
- int step;
- int layer;
- Point(int x=1,int y=1,int step=0,int layer=0):x(x),y(y),step(step),layer(layer) {}
- };
- int ans()
- {
- queue<Point>Q;
- memset(vis,0,sizeof(vis));
- Point a(1,1,0,0);
- Point end_point(n,m);
- Q.push(a);
- vis[1][1][0]=true;
- while(!Q.empty())
- {
- Point now=Q.front();
- Q.pop();
- if(now.x==end_point.x&&now.y==end_point.y)
- return now.step;
- for(int i=0; i<4; i++)
- {
- int x=dx[i]+now.x;
- int y=dy[i]+now.y;
- int layer=now.layer;
- if(map[x][y])
- layer++;//因为每次只会移动一步。而且遇见一层墙,所以加加。
- else
- layer=0;
- if(layer<=k&&!vis[x][y][layer]&&x>=1&&y>=1&&x<=n&&y<=m)
- {
- vis[x][y][layer]=true;
- Q.push(Point(x,y,now.step+1,layer));
- }
- }
- }
- return -1;
- }
- int main()
- {
- cin>>t;
- while(t--)
- {
- cin>>n>>m>>k;//输入行和列以及k值!
- for(int i=1; i<=n; i++)
- for(int j=1; j<=m; j++)
- cin>>map[i][j];//输入地图
- cout<<ans()<<endl;
- }
- return 0;
- }
最新文章
- paip.提升中文分词准确度---新词识别
- EWM一个仓库号对应ERP多个PLANT的配置
- Apache Spark源码走读之11 -- sql的解析与执行
- OSVERSIONINFO
- android 启动时的短暂黑屏解决
- C#遍历窗体控件(原文出自http://www.liangshunet.com/ca/201403/286434593.htm)
- grep命令參数及使用方法
- 浅谈《Linux就该这么学》
- Java Spring Boot VS .NetCore (八) Java 注解 vs .NetCore Attribute
- 关于postman各功能的说明及用法以及批量执行
- 归并排序(MergeSort)和快速排序(QuickSort)的一些总结问题
- jmeter5.0生成html报告 快速入门
- cf1106E 线性dp+multiset
- 提bug
- 【mysql】一个很小但很影响速度的地方
- jquery插件:select、checkbox、radio的美化
- 用U盘制作启动盘后空间变小的恢复方法
- 获取指定时间的Date对象,IE和Chrome的区别(兼容IE)
- Centos下配置单元测试工具gtest
- c#数和二叉树
热门文章
- JAVA笔记整理(七),JAVA几个关键字
- 【视频】谷歌大佬30分钟让你入门机器学习(2019谷歌I/O资源分享)
- Linux命令——ar
- [ansible-playbook]4 持续集成环境之分布式部署利器 ansible playbook学习
- 【经典/基础BFS+略微复杂的题意】PAT-L3-004. 肿瘤诊断
- js获取此刻时间或者把日期格式时间转换成字符串格式的时间
- Mac+appium+iOS 环境搭建
- unity里blit的load store action设置
- czy的后宫——矩阵快速幂优化DP
- Python中日志logging模块