洛谷 P1126 机器人搬重物

这篇具有很好参考价值的文章主要介绍了洛谷 P1126 机器人搬重物。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

机器人移动学会(RMI)现在正尝试用机器人搬运物品。机器人的形状是一个直径 1.6 米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个 N×M 的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有:

  • 向前移动 1 步(Creep);
  • 向前移动 2 步(Walk);
  • 向前移动 3 步(Run);
  • 向左转(Left);
  • 向右转(Right)。

每个指令所需要的时间为 1 秒。请你计算一下机器人完成任务所需的最少时间。

输入格式

第一行为两个正整数 N,M (1≤N,M≤50),下面 N 行是储藏室的构造,0 表示无障碍,1 表示有障碍,数字之间用一个空格隔开。接着一行有 4 个整数和 1 个大写字母,分别为起始点和目标点左上角网格的行与列,起始时的面对方向(东 E,南 S,西 W,北 N),数与数,数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出格式

一个整数,表示机器人完成任务所需的最少时间。如果无法到达,输出 −1−1。

洛谷 P1126 机器人搬重物,题组,算法

输入输出样例

输入 #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

这题耗时2个多小时终于算是做出来了

洛谷 P1126 机器人搬重物,题组,算法

 这题求最少时间,很容易想到用广度搜索,然而这题与一般的找出口最短时间稍微有点不同,

1.需要考虑转变方向所消耗的时间。

2.每次移动不止移动一步。

这里我个人觉得还是要抓住广搜的原理,这题中,广搜是把一秒能发生的运动的所有情况都存下来,这题中,不管是改变方向,还是改变位置,都是一秒发生的,所以都要进行入队操作,我们的标记数组也不单单只标记坐标,还要判断每个坐标的4个方向是否都使用过,多了一个考虑的因素(这里我用三维数组标记),导致题目的难度上升。

这题还有一些需要注意的;

1.因为存在一秒移动多个位置,所以不单单只判断到达的那个点是否是障碍物,还需要判断移动的过程中是否遇到障碍物。

2.终点和起点可能重合(特判就行)

3.机器人占四个格子,只有组成正方形的4个格子都为0才能移动(这里刚开始的时候处理一下就行)

具体操作看代码

AC代码文章来源地址https://www.toymoban.com/news/detail-817549.html

#include<stdio.h>
struct nb {//结构体列队
	int x, y;//x为横坐标,y为纵坐标
	int s, f;//s为步数,//f为方向
}link[850100];
int n, m, x, y, p, q, f;
int hard = 1, tail = 1;
int a[52][52], b[52][52], book[52][52][91];
int main()
{
	int i, j;
	scanf("%d %d", &n, &m);//输入矩阵大小
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			scanf("%d", &a[i][j]);
	for(i=1;i<n;i++)//特殊处理只有4个格子组成的正方形都为0,机器人才能通过
		for (j = 1; j < m; j++)
		{
			if (a[i][j] == 0 && a[i][j + 1] == 0 && a[i + 1][j] == 0 && a[i + 1][j + 1] == 0)
				b[i][j] = 0;
			else
				b[i][j] = 1;
		}
	scanf("%d %d %d %d", &x, &y, &p, &q);//输入起点,终点
	getchar();
	scanf("%c", &f);//起始朝向
	if (x == p && y == q)//特判起点终点是否重合
	{
		printf("0");
		return 0;
	}
	//起始点入队
	link[tail].x = x; link[tail].y = y;
	link[tail].s = 0; 
	if (f == 'E') link[tail].f = 1;//f=1表示东方向,2表示南,3表示西,4表示北
	else if(f == 'S') link[tail].f = 2;
	else if (f == 'W') link[tail].f = 3;
	else  link[tail].f = 4;
	book[x][y][link[tail].f] = 1; tail++;
	int flag = 0;//flag用于判断是否找到出口
	//广搜核心代码
	while (hard < tail)
	{
		//先广度搜索方向
		for (i = 0; i <= 1; i++)
		{
			int tf;
			if (i == 0)//0表示左转
			{
				tf = link[hard].f + 1;
				if (tf == 5)
					tf = 1;
			}
			else//右转
			{
				tf = link[hard].f - 1;
				if (tf == 0)
					tf = 4;
			}
			if (book[link[hard].x][link[hard].y][tf] == 0)//如果这个方向没有入队,进行入队操作
			{
				link[tail].x = link[hard].x;
				link[tail].y = link[hard].y;
				link[tail].s = link[hard].s + 1;
				link[tail].f = tf;
				book[link[hard].x][link[hard].y][tf] = 1;
				tail++;
			}
		}
		//广度搜索不同移动距离
		for (i = 3; i >= 1; i--)
		{
			int tx, ty;
			int fl = 0;//判断移动期间是否遇到障碍物,0为没有遇到
			if (link[hard].f == 1)//link[hard].f大小不同移动方向不同
			{
				tx = link[hard].x;
				ty = link[hard].y + i;
				if (tx<1 || tx>n - 1 || ty<1 || ty>m - 1)//是否越界
					continue;
				for (j = link[hard].y + 1; j <= ty; j++)//判断是否遇到障碍物
				{
					if (b[tx][j] == 1)
					{
						fl = 1;
						break;
					}
				}
			}
			else if (link[hard].f == 2)
			{
				tx = link[hard].x + i;
				ty = link[hard].y;
				if (tx<1 || tx>n - 1 || ty<1 || ty>m - 1)//是否越界
					continue;
				for (j = link[hard].x + 1; j <= tx; j++)//判断是否遇到障碍物
				{
					if (b[j][ty] == 1)
					{
						fl = 1;
						break;
					}
				}
			}
			else if (link[hard].f == 3)
			{
				tx = link[hard].x;
				ty = link[hard].y - i;
				if (tx<1 || tx>n - 1 || ty<1 || ty>m - 1)//是否越界
					continue;
				for (j = link[hard].y - 1; j >= ty; j--)//判断是否遇到障碍物
				{
					if (b[tx][j] == 1)
					{
						fl = 1;
						break;
					}
				}
			}
			else
			{
				tx = link[hard].x - i;
				ty = link[hard].y;
				if (tx<1 || tx>n - 1 || ty<1 || ty>m - 1)//是否越界
					continue;
				for (j = link[hard].x - 1; j >= tx; j--)//判断是否遇到障碍物
				{
					if (b[j][ty] == 1)
					{
						fl = 1;
						break;
					}
				}
			}
			if (book[tx][ty][link[hard].f] == 0 && fl == 0)//如果这个点的这个方向第一次遇到且到这个点期间没有遇到障碍物
			{
				//入队操作+标记
				link[tail].x = tx;
				link[tail].y = ty;
				link[tail].s = link[hard].s + 1;
				link[tail].f = link[hard].f;
				book[tx][ty][link[tail].f] = 1;
				tail++;
				if (tx == p && ty == q)//如果找到出口标记并提前结束
				{
					flag = 1;
					break;
				}
			}
		}
		hard++;//一个点广搜完,判断下一个点
		if (flag == 1)//找到出口,提前结束
			break;
	}
	if (flag == 1)//找到输出最短时间
		printf("%d", link[tail - 1].s);
	else//没找到输出-1
		printf("-1");
	return 0;
}

到了这里,关于洛谷 P1126 机器人搬重物的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 机器人集群控制算法概述

    机器人集群控制算法是指一组算法,用于协调和控制多个机器人协同工作,以完成特定任务或达到特定目标。以下是一些常见的机器人集群控制算法: 集群协同行为算法: 领航者/跟随者(Leader/Follower): 一个机器人被指定为领导者,其他机器人跟随领导者的运动。这种方法

    2024年03月15日
    浏览(52)
  • 机器人控制算法——TEB算法—Obstacle Avoidance and Robot Footprint Model(避障与机器人足迹模型)

    1.1处罚条款 避障是作为整体轨迹优化的一部分来实现的。显然,优化涉及到找到指定成本函数(目标函数)的最小成本解(轨迹)。简单地说:如果一个计划的(未来)姿势违反了与障碍物的期望分离,那么成本函数的成本必须增加。理想情况下,在这些情况下,成本函数值

    2024年02月06日
    浏览(46)
  • 算法题——机器人的运动范围

    声明 该系列文章仅仅展示个人的解题思路和分析过程,并非一定是优质题解,重要的是通过分析和解决问题能让我们逐渐熟练和成长,从新手到大佬离不开一个磨练的过程,加油! 原题链接 机器人的运动范围 https://leetcode.cn/leetbook/read/illustration-of-algorithm/9h6vo2/ 算法分析 图

    2024年02月11日
    浏览(43)
  • 【多机器人】基于A_Star算法实现多机器人路径规划附Matlab代码

     ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进, 代码获取、论文复现及科研仿真合作可私信。 🍎个人主页:Matlab科研工作室 🍊个人信条:格物致知。 更多Matlab完整代码及仿真定制内容点击👇 智能优化算法       神经网络预测       雷达通信    

    2024年02月04日
    浏览(51)
  • 遨博协作机器人高级编程 - 遨博机器人SDK用户自定义算法接口介绍与使用

    目录 一、简介 二、环境版本 三、开发环境部署 1.二次开发资料下载 2. AUBO PE编程仿真环境配置 四、linux C++ SDK示例 1. 编程环境 2. 加载C++ SDK工程 3. linux C++ SDK 文件构成 4.运行SDK示例 五、构建用户自定义算法SDK示例工程 1.Linux C++ SDK透传接口 2.  创建新项目 3.导入遨博机器人

    2024年02月14日
    浏览(53)
  • 【算法-数组-pyhton】模拟行走机器人

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月12日
    浏览(37)
  • 智能快递机器人—— 人脸识别算法设计

    ** 计算机系统的介绍   智能快递机器人是一种以自动导航轮式小车为载体,搭载人脸识别检测模块以及储存箱体的智能运输机器人。其可以实现GPS自动导航,箱门自动开合,识别取件人面部等功能,主要运用于写字楼,小区,高校宿舍楼等物流运输的终端场所,研究目的在

    2024年02月07日
    浏览(51)
  • 【机器人状态估计】粒子滤波算法介绍

    问题分类:位姿追踪、局部定位、全局定位;静态、动态环境定位;单一机器人定位、多机器人定位。 贝叶斯滤波框架: 定位置信度与运动模型卷积,两次独立估计值的整合比单一估计值使系统状态确定性更高。 基本思路 随机产生M个粒子(如M=1000),每个粒子表示状态变

    2024年02月22日
    浏览(39)
  • SLAM+路径规划:巡检机器人算法设计

    标题:Research on SLAM and Path Planning Method of Inspection Robot in Complex Scenarios 作者:Xiaohui Wang,Xi Ma,Zhaowei Li 编译:东岸因为 编辑:郑欣欣@一点人工一点智能 入群邀请:7个专业方向交流群+1个资料需求群 原文:SLAM+路径规划:巡检机器人算法设计 工厂安全检查对于保持生产环境

    2024年02月03日
    浏览(46)
  • 【算法】行星碰撞&机器人碰撞(栈的使用)

    本文记录了两个使用栈来处理碰撞问题的算法题目。 https://leetcode.cn/problems/asteroid-collision/ 对于这种题目,各个元素分别会向左或向右移动,可以使用栈模拟碰撞的过程。 由于从左往右进行遍历,因此遍历当前元素时,如果它是向右移动的,就只可能会碰撞到它右边还没有被

    2024年02月16日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包