hiho一下第142周《扫地机器人》题目分析

10
1

《扫地机器人》题目分析

这个题目是一道比较复杂的计算几何题目。

首先我们要想明白机器人能完整清扫的充分必要条件是什么?

我们分析一些情况之后,就会有一个直观的判断:如果机器人能贴着边界转一圈回到出发点,那么就可以完整清扫整个房间。反之,如果机器人在贴着边界移动过程中会受到阻碍,那么就没办法完整清扫整个房间。

对于判断机器人能否贴着边界转一圈这个问题,我们可以把它分解成若干个子问题:判断机器人能否贴着边界从一个转角移动到下一个转角。如果对于某次转角到转角的移动受到阻碍,那就转一圈也一定会受到阻碍;反之如果每次转角到转角都不受阻碍,那么转一圈也不会受到阻碍。

当机器人从一个转角移动到下一个转角时,机器人扫过的范围一定是一个矩形。当机器人在上述移动中遇到阻碍时,这个矩形一定与某段房间边界相交。

于是我们有了一个解决本题的思路:
1. 假设机器人顺时针转一圈,对于相邻的两个转角A和B,计算机器人从A到B时扫过的矩形位置。
2. 判断该矩形是否与某段房间边界相交。

对于第一个问题,我们可以考虑机器人开始和结束的位置,也就是机器人在A转角时的位置和机器人在B转角时的位置。这里位置是要求出机器人4个顶点的坐标。如果我们知道机器人分别处于转角A和转角B时的4个顶点坐标,那么这8个坐标中最左上的点就是扫过矩形的左上角,最右下的点就是扫过矩形的右下角。

于是问题进一步简化为:对于每一个转角A,求机器人在A时4个顶点的坐标。

首先我么把转角分为内角(顺时针转90度)和外角(顺时针转270度)。例如上图中蓝圈圈住的转角是内角,红圈圈住的转角是外角。其次对于一个转角A,我们可以将转角A视为由两条有向线段收尾相接形成的。我们把前一条有向线段的方向称为“入角方向”,后一条有向线段的方向称为“出角方向”。

如果A是内角,那么机器人一个顶点a一定在A点处,另外一个顶点b一定在a沿着出角方向移动M处,另外一个顶点c一定在a沿着入角方向反向移动M处。如果A是外角,同样机器人一个顶点a一定在A点处,另外一个顶点b一定在a沿着出角方向反向移动M处,另外一个顶点c一定在a沿着入角方向移动M处。

于是我们就可以求出机器人在一个转角时,4个顶点的位置。

第二个问题,是一个特殊的判断矩形与线段相交的问题。特殊在矩形的边和线段都是平行于坐标轴的。比较简单的方法是讨论什么情况下矩形与线段不相交。可以发现如果不相交,那么矩形与线段一定在X轴方向或Y轴方向上是相离的。

最后需要说明的一点是:有些判断方法是有漏洞的,比如只判断机器人在转角时是否与房间边界相交。你能想到反例吗?

  • 判断机器人在转角时刻(机器人一个顶点与房间顶点重合)以及该时刻的下一个时刻是否与房间边界相见应该是没有漏洞的

  • 添加评论
  • reply

3 answer(s)

0

0

so easy,一个凹子从左下到右下,机器人很窄太高就gg

0

想了一想,如果只是检验是否能扫清全屋,应该是没有漏洞的。粗略的讲,如果有反例,则必定是矩形中间部分撞到至少一对距离相对更近的相邻转角,那么这种问题也一定会在这对距离相对更近的相邻转角时的机器人时刻被检测出来,否则必有更小的一对相邻转角。。无穷递降又房间转角有限,知必能被测出。例如凹字的左下到右下的问题必能被2相邻反角时刻测出。

write answer 切换为英文 切换为中文


转发分享