【每日一题】1041. 困于环中的机器人

1041. 困于环中的机器人 - 力扣（LeetCode）

在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。注意:

• 北方向 是y轴的正方向。
• 南方向 是y轴的负方向。
• 东方向 是x轴的正方向。
• 西方向 是x轴的负方向。

机器人可以接受下列三条指令之一：

• "G"：直走 1 个单位
• "L"：左转 90 度
• "R"：右转 90 度

机器人按顺序执行指令 instructions，并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。

示例 1：

输入：instructions = "GGLLGG"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
“L”:逆时针旋转90度。位置:(0,2).方向:西。
“L”:逆时针旋转90度。位置:(0,2)方向:南。
“G”:移动一步。位置:(0,1)方向:南。
“G”:移动一步。位置:(0,0)方向:南。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(0,2)——>(0,1)——>(0,0)。
在此基础上，我们返回true。

示例 2：

输入：instructions = "GG"
输出：false
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
重复这些指示，继续朝北前进，不会进入循环。
在此基础上，返回false。

示例 3：

输入：instructions = "GL"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“L”:逆时针旋转90度。位置:(0,1).方向:西。
“G”:移动一步。位置:(- 1,1)方向:西。
“L”:逆时针旋转90度。位置:(- 1,1)方向:南。
“G”:移动一步。位置:(- 1,0)方向:南。
“L”:逆时针旋转90度。位置:(- 1,0)方向:东方。
“G”:移动一步。位置:(0,0)方向:东方。
“L”:逆时针旋转90度。位置:(0,0)方向:北。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(- 1,1)——>(- 1,0)——>(0,0)。
在此基础上，我们返回true。

 

class Solution {char location = 'N';int x=0,y=0;public boolean isRobotBounded(String instructions) {int len = instructions.length();for(int j = 0 ;j < 4 ; ++j)for(int i = 0; i < len ; ++i) {move(instructions.charAt(i));}if(x==0&&y==0) return true;return false;}public void move (char a) {if(a == 'L') {switch(location) {case 'N' : location = 'W'; break;case 'W' : location = 'S'; break;case 'S' : location = 'E'; break;case 'E' : location = 'N'; break;}} else if(a == 'R') {switch(location) {case 'N' : location = 'E'; break;case 'W' : location = 'N'; break;case 'S' : location = 'W'; break;case 'E' : location = 'S'; break;}} else if(a == 'G') {switch(location) {case 'N' : y+=1; break;case 'W' : x-=1; break;case 'S' : y-=1; break;case 'E' : x+=1; break;}}}
}

这道题最主要在于理解“循环”。环，不是有环就可以，而是要存在让机器人走不出来的环。再者，题目中还说到，机器人会不断重复执行一开始给出的指令序列。那么，只在走动过程中有环行不行呢？答案是不行的。必须要能以（0，0）开头组成一个大环，如果只是在行进中走入一个环中，那么下一次循环的时候一定会走出来的，例如下图：

 所以，关键就在于能不能在行走过程中的最后一个指令回到（0，0）。行走过程只需要模拟即可。模拟的同时对x，y进行加减操作。但是，这里还存在一个问题，就是序列不够的情况，有可能一个序列只有“GL”两个，或者只有“GLGL”两个。如果没有行走的指令，那肯定会循环，但一旦有行走的指令，即便指令再怎么少，最多只需要循环4次就可以知道到底能否回到原点构成环。所以，只需要将指令序列循环4次，再去判断x，y即可。

该题的题解则是对执行一次指令之后机器人所处的方向和位置进行判断，以此来推断是否可以组成环，大家做完题也可以去看看。