題目
難度：★★☆☆☆
類型：幾何枢贿、二維數(shù)組
機(jī)器人在一個(gè)無(wú)限大小的網(wǎng)格上行走俺猿，從點(diǎn) (0, 0) 處開始出發(fā)乔煞，面向北方褂傀。該機(jī)器人可以接收以下三種類型的命令：
-2：向左轉(zhuǎn) 90 度
-1：向右轉(zhuǎn) 90 度
1 <= x <= 9：向前移動(dòng) x 個(gè)單位長(zhǎng)度
在網(wǎng)格上有一些格子被視為障礙物啸罢。
第 i 個(gè)障礙物位于網(wǎng)格點(diǎn) (obstacles[i][0], obstacles[i][1])
如果機(jī)器人試圖走到障礙物上方编检，那么它將停留在障礙物的前一個(gè)網(wǎng)格方塊上，但仍然可以繼續(xù)該路線的其余部分扰才。
返回從原點(diǎn)到機(jī)器人的最大歐式距離的平方允懂。
提示
0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
答案保證小于 2 ^ 31
示例
示例 1
輸入: commands = [4,-1,3], obstacles = []
輸出: 25
解釋: 機(jī)器人將會(huì)到達(dá) (3, 4)
示例 2
輸入: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
輸出: 65
解釋: 機(jī)器人在左轉(zhuǎn)走到 (1, 8) 之前將被困在 (1, 4) 處
解答
步長(zhǎng)問題。因?yàn)樯婕暗秸系K物的判斷衩匣，我們最好每次只走一步蕾总，而不是整條線路，邊走邊判斷前方是否有障礙物琅捏，模擬真實(shí)情況生百。
方向問題。機(jī)器人有四個(gè)方向可以行走柄延，且初始方向是北蚀浆，對(duì)每一個(gè)方向，向前走一步后的坐標(biāo)計(jì)算方式都是不同的，我們定義了方向列表市俊，表達(dá)向北杨凑、東、南摆昧、西（順時(shí)針）四個(gè)方向走一步后撩满，機(jī)器人的坐標(biāo)同上一步的區(qū)別， 定義dx = [0, 1, 0, -1] 绅你，dy = [1, 0, -1, 0]伺帘，使用di進(jìn)行方向索引（初始值為零，對(duì)應(yīng)于北方向）忌锯。例如曼追，向北走一步，對(duì)應(yīng)位移（0汉规， 1），相當(dāng)于x軸方向上+0驹吮，y軸方向上+1针史，我們通過(guò)di除以4取余的方式來(lái)確定左轉(zhuǎn)或右轉(zhuǎn)后的方向，以確保di索引在0到3之間碟狞。
障礙物啄枕。我們需要將障礙物設(shè)置成集合形式，這樣可以加速程序運(yùn)行族沃，方便進(jìn)行快速查找频祝。
循環(huán)。遍歷每一個(gè)控制量脆淹，對(duì)于左轉(zhuǎn)和右轉(zhuǎn)分別處理常空，對(duì)于前進(jìn)需要一步一步進(jìn)行，同步判斷前方是否有障礙物盖溺，如果有漓糙，則繼續(xù)執(zhí)行下一個(gè)控制指令，否則繼續(xù)前進(jìn)下去烘嘱。
class Solution:
def robotSim(self, commands, obstacles):
"""
:param commands: List[int]
:param obstacles: List[List[int]]
:return: int
"""
dx = [0, 1, 0, -1] # 北昆禽、東、南蝇庭、西
dy = [1, 0, -1, 0]
x = y = di = 0
obstacles = set(map(tuple, obstacles))
ans = 0
for cmd in commands:
if cmd == -2: # 左轉(zhuǎn)
di = (di - 1) % 4
elif cmd == -1: # 右轉(zhuǎn)
di = (di + 1) % 4
else:
for k in range(cmd):
if (x + dx[di], y + dy[di]) not in obstacles:
x += dx[di]
y += dy[di]
ans = max(ans, x * x + y * y)
return ans
面向?qū)ο笫蔷幊痰睦硐虢Y(jié)構(gòu)醉鳖，我們把機(jī)器人封裝成一個(gè)類，機(jī)器人類具有：
三個(gè)實(shí)例變量：可能的方向列表哮内，當(dāng)前方向索引（id盗棵，0到3），當(dāng)前位置（location）；
兩個(gè)屬性：獲得當(dāng)前方向（direction）漾根，獲得當(dāng)前位置距離原點(diǎn)的平方和（dist_square）泰涂；
三個(gè)方法：左轉(zhuǎn)（turn_left），右轉(zhuǎn)（turn_right）辐怕，向前走一步（one_step）
向前走一步方法有一個(gè)輸入?yún)?shù)（have_a_try）逼蒙，如果設(shè)置為True，則不會(huì)修改機(jī)器人的當(dāng)前位置寄疏，否則會(huì)修改是牢，默認(rèn)為False。
我們用構(gòu)建的機(jī)器人類重構(gòu)上述代碼陕截，可以獲得更加簡(jiǎn)潔清晰易懂的表達(dá)效果驳棱，但是在這道題上執(zhí)行速度略有下降。這種面向?qū)ο蟮乃枷胫档脤W(xué)習(xí)农曲。
class Robot:
def __init__(self):
self.directions = ['north', 'east', 'south', 'west']
self.id = 0
self.location = (0, 0)
def turn_left(self):
self.id = (self.id - 1) % 4
def turn_right(self):
self.id = (self.id + 1) % 4
@property
def direction(self):
return self.directions[self.id]
@property
def dist_square(self):
return sum(map(lambda x: x*x, self.location))
def one_step(self, have_a_try=False): # 向一個(gè)方向移動(dòng)一步
loc = self.location
if self.direction == 'north':
loc = self.location[0], self.location[1] + 1
elif self.direction == 'east':
loc = self.location[0] + 1, self.location[1]
elif self.direction == 'south':
loc = self.location[0], self.location[1] - 1
elif self.direction == 'west':
loc = self.location[0] - 1, self.location[1]
if not have_a_try:
self.location = loc
return loc
class Solution:
def robotSim(self, commands, obstacles):
"""
:param commands: List[int]
:param obstacles: List[List[int]]
:return: int
"""
robot = Robot()
obstacles = set(map(tuple, obstacles))
ans = 0 # 結(jié)果
for cmd in commands:
if cmd == -2: # 左轉(zhuǎn)
robot.turn_left()
elif cmd == -1: # 右轉(zhuǎn)
robot.turn_right()
else:
for k in range(cmd):
if robot.one_step(have_a_try=True) in obstacles:
continue
else:
robot.one_step()
ans = max(ans, robot.dist_square)
return ans
如有疑問或建議社搅，歡迎評(píng)論區(qū)留言~
