洛谷——P1126 机器人搬重物
2024-09-07 17:34:19
P1126 机器人搬重物
题目描述
机器人移动学会(RMI)现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个N*M的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有:向前移动1步(Creep);向前移动2步(Walk);向前移动3步(Run);向左转(Left);向右转(Right)。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。
输入输出格式
输入格式:
输入的第一行为两个正整数N,M(N,M<=50),下面N行是储藏室的构造,0表示无障碍,1表示有障碍,数字之间用一个空格隔开。接着一行有四个整数和一个大写字母,分别为起始点和目标点左上角网格的行与列,起始时的面对方向(东E,南S,西W,北N),数与数,数与字母之间均用一个空格隔开。终点的面向方向是任意的。
输出格式:
一个整数,表示机器人完成任务所需的最少时间。如果无法到达,输出-1。
输入输出样例
输入样例#1:
9 10 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 7 2 2 7 S
输出样例#1
12
真的是很不错的搜索题(泪奔、、、)
由于机器人是个恶心的圆形,那我们们在判断某个位置是否可以走的时候我们就需要判断这个圆形所占的位置是否可以走,然后在进行移动。
有一个很鬼畜的地方就是我们必须要向经行正面移动才能进行方向的转动,不然会wa好几个点
然后我们要用一个数组记录到当前点且为到当前方向是否已经到达过,如果已经到达过,直接continue,因为我们知道bfs首先到达的一定是最近的,这样我们就可以做到一个很好的剪枝
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 100 using namespace std; char ch; ]; int n,m,d,sx,sy,ex,ey,dis[N][N]; ][]={{,,},{-,-,-},{,,},{,,}}; ][]={{-,-,-},{,,},{,,},{,,}}; int read() { ,f=; char ch=getchar(); ') ch=getchar(); +ch-',ch=getchar(); return x*f; } struct Que { int x,y,d,step; }que; queue<Que>q; int main() { n=read(),m=read(); ;i<=n;i++) ;j<=m;j++) { vis[i][j]=read(); if(vis[i][j]) vis[i-][j]=vis[i-][j-]=vis[i][j-]=true; } sx=read(),sy=read(); ex=read(),ey=read(); cin>>ch;vis[sx][sy]=; ; ; ; ; que.x=sx,que.y=sy; dis[sx][sy]=que.step=; vist[sx][sy][que.d]=true; q.push(que); while(!q.empty()) { Que p=q.front();q.pop(); ;} ;i<;i++) { int x=p.x+xx[p.d][i],y=p.y+yy[p.d][i]; ||y<||x>=n||y>=m||vis[x][y]) break; if(vist[x][y][p.d]) continue; vist[x][y][p.d]=true; que.x=x,que.y=y,que.d=p.d,que.step=p.step+; q.push(que); } que.x=p.x,que.y=p.y,que.d=p.d+,que.step=p.step+; ==) que.d=; if(!vist[que.x][que.y][que.d]) vist[que.x][que.y][que.d]=true,q.push(que); que.x=p.x,que.y=p.y,que.d=p.d-,que.step=p.step+; ==-) que.d=; if(!vist[que.x][que.y][que.d]) vist[p.x][p.y][p.d]=true,q.push(que); } printf("-1"); ; }
最新文章
- JS三大特性
- Reflector反编译WinForm程序重建项目资源和本地资源
- js 中json字符串转化json对象
- c#启动进程
- C#应用Newtonsoft.Json操作json
- Flex布局摆脱float带来的布局问题
- How to check for and disable Java in OS X
- mongodb or操作与连接池
- DIY.NETORM帧——技术储备(1)Attribute
- MySQL 权限与用户表
- 深入了解Object.defineProperty
- python 数据可视化 -- 真实数据的噪声平滑处理
- js中表达式 >;>;>; 0 浅析
- 百度编辑器UEditor使用方法
- springMVC的全局异常设置
- java web 三大核心组件Filter
- Spring Kafka中关于Kafka的配置参数
- 3.6Python数据处理篇之Numpy系列(六)---Numpy随机函数
- Qt下多线程日之类
- Python 基础day3
热门文章
- thinkcmf5更新模板代码分析,解决模板配置json出错导致数据库保存的配置项内容丢失问题
- UVa - 1592 Database(STL,优化)
- 使用jquery.layout.js构建页眉/页脚/左侧导航/中间展示内容的网页结构
- 远程连接MYSQL8.0服务器问题
- POJ - 1321 深度优先搜索入门
- 认识Function.prototype.call
- 模拟 - BZOJ 1510 [POI2006] Kra-The Disks
- 关于windows服务的编写/安装/与调试
- 转 关于oracle 分区表 表空间以及索引的总结
- JS手风琴特效