題目鏈接

Leetcode.1041 困于環(huán)中的機(jī)器人 Rating ： 1521

題目描述

在無(wú)限的平面上，機(jī)器人最初位于 (0, 0) 處，面朝北方。注意:

• 北方向 是y軸的正方向。
• 南方向 是y軸的負(fù)方向。
• 東方向 是x軸的正方向。
• 西方向 是x軸的負(fù)方向。

機(jī)器人可以接受下列三條指令之一：

• "G"：直走 1 個(gè)單位
• "L"：左轉(zhuǎn) 90 度
• "R"：右轉(zhuǎn) 90 度

機(jī)器人按順序執(zhí)行指令 instructions，并一直重復(fù)它們。

只有在平面中存在環(huán)使得機(jī)器人永遠(yuǎn)無(wú)法離開(kāi)時(shí)，返回 true。否則，返回 false。

示例 1：

輸入：instructions = “GGLLGG”
輸出：true
解釋?zhuān)簷C(jī)器人最初在(0,0)處，面向北方。
“G”:移動(dòng)一步。位置:(0,1)方向:北。
“G”:移動(dòng)一步。位置:(0,2).方向:北。
“L”:逆時(shí)針旋轉(zhuǎn)90度。位置:(0,2).方向:西。
“L”:逆時(shí)針旋轉(zhuǎn)90度。位置:(0,2)方向:南。
“G”:移動(dòng)一步。位置:(0,1)方向:南。
“G”:移動(dòng)一步。位置:(0,0)方向:南。
重復(fù)指令，機(jī)器人進(jìn)入循環(huán):(0,0)——>(0,1)——>(0,2)——>(0,1)——>(0,0)。
在此基礎(chǔ)上，我們返回true。

示例 2：

輸入：instructions = “GG”
輸出：false
解釋?zhuān)簷C(jī)器人最初在(0,0)處，面向北方。
“G”:移動(dòng)一步。位置:(0,1)方向:北。
“G”:移動(dòng)一步。位置:(0,2).方向:北。
重復(fù)這些指示，繼續(xù)朝北前進(jìn)，不會(huì)進(jìn)入循環(huán)。
在此基礎(chǔ)上，返回false。

示例 3：

輸入：instructions = “GL”
輸出：true
解釋?zhuān)簷C(jī)器人最初在(0,0)處，面向北方。
“G”:移動(dòng)一步。位置:(0,1)方向:北。
“L”:逆時(shí)針旋轉(zhuǎn)90度。位置:(0,1).方向:西。
“G”:移動(dòng)一步。位置:(- 1,1)方向:西。
“L”:逆時(shí)針旋轉(zhuǎn)90度。位置:(- 1,1)方向:南。
“G”:移動(dòng)一步。位置:(- 1,0)方向:南。
“L”:逆時(shí)針旋轉(zhuǎn)90度。位置:(- 1,0)方向:東方。
“G”:移動(dòng)一步。位置:(0,0)方向:東方。
“L”:逆時(shí)針旋轉(zhuǎn)90度。位置:(0,0)方向:北。
重復(fù)指令，機(jī)器人進(jìn)入循環(huán):(0,0)——>(0,1)——>(- 1,1)——>(- 1,0)——>(0,0)。
在此基礎(chǔ)上，我們返回true。

提示：

• $1<=instructions.length<=100$
• instructions[i]僅包含 'G', 'L', 'R'

解法：腦筋急轉(zhuǎn)彎+模擬

當(dāng)機(jī)器人執(zhí)行完 $instructions$ 的所有指令后，它所處的位置為 $(x,y)$，方向?yàn)?$dir$。

• $x==0\&\&y==0$，當(dāng)執(zhí)行完指令之后，還是處于原點(diǎn)，說(shuō)明根本就沒(méi)移動(dòng)。所以機(jī)器人不能離開(kāi)，返回 true
• $x\ne 0||y\ne 0$，當(dāng)執(zhí)行完指令之后，方向 $dir$ 是 向南的。當(dāng) 第二輪執(zhí)行結(jié)束的時(shí)候，方向 $dir$ 又會(huì)向北，并且又會(huì)回到原點(diǎn) $(0,0)$。所以機(jī)器人不能離開(kāi)，返回 true
• $x\ne 0||y\ne 0$，當(dāng)執(zhí)行完指令之后，方向 $dir$ 是 向東的。當(dāng) 第四輪執(zhí)行結(jié)束的時(shí)候，方向 $dir$ 又會(huì)向北，并且又會(huì)回到原點(diǎn) $(0,0)$。所以機(jī)器人不能離開(kāi)，返回 true
• $x\ne 0||y\ne 0$，當(dāng)執(zhí)行完指令之后，方向 $dir$ 是 向西的。當(dāng) 第四輪執(zhí)行結(jié)束的時(shí)候，方向 $dir$ 又會(huì)向北，并且又會(huì)回到原點(diǎn) $(0,0)$。所以機(jī)器人不能離開(kāi)，返回 true
• $x\ne 0||y\ne 0$，當(dāng)執(zhí)行完指令之后，方向 $dir$ 是 向北的。那么說(shuō)明機(jī)器人會(huì)一直沿著北面移動(dòng)，所以最后能夠離開(kāi)，返回 false

時(shí)間復(fù)雜度： $O(n)$

C++代碼：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-417400.html

class Solution {
public:
    bool isRobotBounded(string instructions) {
        int d[4][4] = {{0,1} , {1,0} , {0,-1} , {-1,0}};
        //初始位置
        int x = 0 , y = 0;
        //初始指向
        int dir = 0;

        for(auto c:instructions){
            if(c == 'G'){
                x += d[dir][0];
                y += d[dir][1];
            }
            else if(c == 'L'){
                dir = (dir + 3) % 4;
            }
            else if(c == 'R'){
                dir = (dir + 1) % 4;
            }
        }

        return dir != 0 || (x == 0 && y == 0);
    }
};

到了這里，關(guān)于Leetcode.1041 困于環(huán)中的機(jī)器人的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！