Robot POJ - 1376
The GO command has one integer parameter n in {1,2,3}. After receiving this command the robot moves n meters in the direction it faces.
The TURN command has one parameter which is either left or right. After receiving this command the robot changes its orientation by 90o in the direction indicated by the parameter.
The execution of each command lasts one second.
Help researchers of RMI to write a program which will determine the minimal time in which the robot can move from a given starting point to a given destination.
Input
Output
Sample Input
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 south
0 0
Sample Output
12
机器人搬运研究所正在当地商店中使用机器人来运输不同的物品。当然,机器人只需要花费从商店的一个地方到另一个地方旅行所需的最短时间。机器人只能沿着一条直线(轨道)移动。所有轨道形成一个矩形网格。相邻的轨道相隔一米。该商店是一个矩形的N×M米,它完全被这个网格覆盖。最接近商店一侧的跑道距离只有一米。机器人具有直径等于1.6米的圆形形状。轨道穿过机器人的中心。机器人总是面向北,南,西或东。轨道位于南北和东西方向。机器人只能朝它面对的方向移动。它的方向可以在每个轨道交叉处改变。最初机器人站在轨道交叉处。商店中的障碍物是由地面上的1m×1m的碎片组成的。每个障碍物都在由轨道形成的1×1方格内。机器人的运动由两个命令控制。这些命令是GO和TURN。
GO命令在{1,2,3}中有一个整数参数n。接收到这个命令后,机器人按照它所面对的方向移动n米。
TURN命令有一个参数可以是左或右。接收到该命令后,机器人按照参数指示的方向将其方向改变90°。
每个命令的执行持续一秒钟。
帮助RMI的研究人员编写一个程序,该程序将确定机器人从一个给定的起点移动到一个给定的目的地的最短时间。
这个机器人有两种指令走向当前放下走1-3步或者是向左或向右90度转向(不能向后转)。
注意构图,机器人在线上走动,而给的数据是一个一个的方块格子,
标记数组为vis[100][100][4],4代表4个方向
if (!check(nx,ny)) break;这个的break说明如果你前方已经走不通了 那么你就不能再往前走,于是break
这题的方向特别容易卡 要注意
int dx[4]= {-1,0,1,0}; int dy[4]= {0,1,0,-1};
if (b[0]=='n') d=0;
if (b[0]=='e') d=1;
if (b[0]=='s') d=2;
if (b[0]=='w') d=3;
这些都是一一对应关系
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n,m,x1,y1,x2,y2,tu[][],vis[][][],d;
char b[];
struct node {
int x,y,step,fang;
};
int dx[]= {-,,,};
int dy[]= {,,,-};
int check(int x, int y) {
if (x < || x >=n || y < || y >= m || tu[x][y] || tu[x+][y] || tu[x][y+] || tu[x+][y+]) return ;
return ;
}
int bfs() {
queue<node>q;
node a;
a.x=x1,a.y=y1,a.fang=d,a.step=;
vis[a.x][a.y][d]=;
q.push(a);
while(!q.empty()) {
a=q.front();
q.pop();
if (a.x==x2 && a.y==y2) return a.step;
int nx=a.x;
int ny=a.y;
for (int i = ; i < ; i++) {
nx += dx[a.fang];
ny += dy[a.fang];
if (!check(nx, ny))
break;
if (!vis[nx][ny][a.fang]) {
vis[nx][ny][a.fang] = ;
node cnt;
cnt.x = nx, cnt.y = ny;
cnt.fang =a.fang, cnt.step = a.step+;
q.push(cnt);
}
}
for (int i = ; i < ; i++) {
if (max(a.fang, i)-min(a.fang, i) == )
continue;
if (vis[a.x][a.y][i])
continue;
vis[a.x][a.y][i] = ;
node cnt = a;
cnt.fang = i;
cnt.step = a.step+;
q.push(cnt);
}
}
return -;
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
if (n== && m== ) break;
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++)
scanf("%d", &tu[i][j]);
memset(vis, , sizeof(vis));
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
scanf("%s", b);
if (b[]=='n') d=;
if (b[]=='e') d=;
if (b[]=='s') d=;
if (b[]=='w') d=;
printf("%d\n", bfs());
}
return ;
}
最新文章
- mysql_config 问题
- java 递归获取一个目录下的所有文件路径
- Debian
- CodeForces 589A Email Aliases (匹配,水题)
- [HeadFirst-HTMLCSS学习笔记][第六章严格的HTML]
- UVALive 6869(后缀数组)
- TBDR缺点
- Android开发学习之路--UI之自定义布局和控件
- 完全理解 Python 迭代对象、迭代器、生成器(转)
- kafka 重新分配partition
- PHP为什么有人学不会
- 哥们,你真以为你会做这道JVM面试题?
- Oracle 控制文件管理
- .NET 高性能WEB架构-比较容易改造方式 - .NET架构
- ABAP-金额小写转大写
- spring-security-4 (4)spring security 认证和授权原理
- HRBUST1313 火影忍者之~静音 2017-03-06 16:11 39人阅读 评论(0) 收藏
- Spring 并发事务的探究
- BZOJ 3437: 小P的牧场
- 拦截器springmvc防止表单重复提交【2】
热门文章
- Python学习:1.快速搭建python环境
- Hibernate-ORM:04.Hibernate中的get()和load()
- spring boot 中文文档地址
- Borland和Micorsoft的对话(转载自月光软件网)
- jmeter动态获取jsessionid
- 多个Target的使用
- Linux-Shell脚本编程-学习-5-Shell编程-使用结构化命令-if-then-else-elif
- Django学习笔记(一):环境安装与简单实例
- python 动态函数调用及可变参数传入
- 容器基础(五): 实现一个简单容器sdocker