模擬機(jī)器人行走

機(jī)器人在一個(gè)無(wú)限大小的 XY 網(wǎng)格平面上行走，從點(diǎn) 處開(kāi)始出發(fā)，面向北方。該機(jī)器人可以接收以下三種類(lèi)型的命令 ：

• ：向左轉(zhuǎn) 度
• ：向右轉(zhuǎn) 度
• ：向前移動(dòng) 個(gè)單位長(zhǎng)度

在網(wǎng)格上有一些格子被視為障礙物 。第 i 個(gè)障礙物位于網(wǎng)格點(diǎn) 。

機(jī)器人無(wú)法走到障礙物上，它將會(huì)停留在障礙物的前一個(gè)網(wǎng)格方塊上，但仍然可以繼續(xù)嘗試進(jìn)行該路線(xiàn)的其余部分。

返回從原點(diǎn)到機(jī)器人所有經(jīng)過(guò)的路徑點(diǎn)（坐標(biāo)為整數(shù)）的最大歐式距離的平方。（即，如果距離為 ，則返回 ）

注意：

• 北表示 +Y 方向。
• 東表示 +X 方向。
• 南表示 -Y 方向。
• 西表示 -X 方向。

示例 1:

輸入：commands = [4,-1,3], obstacles = []

輸出：25

解釋?zhuān)?機(jī)器人開(kāi)始位于 (0, 0)：

1. 向北移動(dòng) 4 個(gè)單位，到達(dá) (0, 4)
2. 右轉(zhuǎn)
3. 向東移動(dòng) 3 個(gè)單位，到達(dá) (3, 4) 距離原點(diǎn)最遠(yuǎn)的是 (3, 4) ，距離為 32 + 42 = 25

示例 2：

輸入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]

輸出：65

解釋?zhuān)簷C(jī)器人開(kāi)始位于 (0, 0)：

1. 向北移動(dòng) 4 個(gè)單位，到達(dá) (0, 4)
2. 右轉(zhuǎn)
3. 向東移動(dòng) 1 個(gè)單位，然后被位于 (2, 4) 的障礙物阻擋，機(jī)器人停在 (1, 4)
4. 左轉(zhuǎn)
5. 向北走 4 個(gè)單位，到達(dá) (1, 8) 距離原點(diǎn)最遠(yuǎn)的是 (1, 8) ，距離為 12 + 82 = 65

提示：

題解思路

如示例2圖示：

代碼實(shí)現(xiàn)的難點(diǎn)在于方向的切換，這一類(lèi)題目我們統(tǒng)一采用 「方向數(shù)組」 來(lái)處理。

我們定義當(dāng)前方向?yàn)?code>dir，可取值為 {0，1，2，3}；分別代表 {北，東，南，西}。見(jiàn)上圖。

那么當(dāng)機(jī)器人遇到改變方向的命令時(shí)，我們直接修改dir的值即可：

然后再分別在 x 和 y 兩個(gè)方向上定義兩個(gè)方向數(shù)組，以Java為例：

int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};

1. 方向?yàn)?code>北(0)時(shí)：每次前進(jìn) x 不變，y 加一。
2. 方向?yàn)?code>東(1)時(shí)：每次前進(jìn) x 加一，y 不變。
3. 方向?yàn)?code>南(2)時(shí)：每次前進(jìn) x 不變，y 減一。
4. 方向?yàn)?code>西(3)時(shí)：每次前進(jìn) x 減一，y 不變。

代碼實(shí)現(xiàn)

Java

class Solution {

    private Set< Integer > obstacleSet = new HashSet<  >();
    private int factor = 100000;

    public int robotSim(int[] commands, int[][] obstacles) {

        genObstacleSet(obstacles);

        // 當(dāng)前方向，北：0， 東：1，南：2， 西：3
        int dir = 0;

        // 方向數(shù)組
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        // 機(jī)器人位置
        int x = 0, y = 0; 
        int ans = 0;
        for(int command : commands){
            if(command == -2){
                dir = (dir + 3) % 4;
                continue;
            }if(command == -1){
                dir = (dir + 1) % 4;
                continue;
            }
            for(int i = 0; i < command; i++){
                // 如果遇到障礙物，停止在當(dāng)前位置
                if(isObstacle(x + dx[dir], y + dy[dir])){
                    break;
                }
                x += dx[dir];
                y += dy[dir];
                ans = Math.max(ans, x * x + y * y);
            }
        }

        return ans;

    }

    // 判斷是否是障礙物
    private boolean isObstacle(int x, int y){
        return obstacleSet.contains(factor * x + y);
    }

    private void genObstacleSet(int[][] obstacles){

        for(int[] obstacle : obstacles){
            obstacleSet.add(factor * obstacle[0] + obstacle[1]);
        }

    }
}

Go

func robotSim(commands []int, obstacles [][]int) int {

    // 初始化障礙點(diǎn)位
    obstacleMap := make(map[[2]int]bool)
    for _, obstacle := range obstacles {
        obstacleMap[[2]int{obstacle[0], obstacle[1]}] = true
    }

    // 當(dāng)前方向
    dir := 0

    // 方向數(shù)組
    dx, dy := []int{0, 1, 0, -1}, []int{1, 0, -1, 0}

    // 當(dāng)前位置
    x, y := 0, 0

    // 答案
    ans := 0

    for _, command := range commands {
        if command == -2 {
            dir = (dir + 3) % 4
            continue
        }

        if command == -1 {
            dir = (dir + 1) % 4
            continue
        }

        for i := 0; i < command; i++ {
            // 遇到障礙物
            if _, ok := obstacleMap[[2]int{x + dx[dir], y + dy[dir]}]; ok {
                break;
            }
            x += dx[dir]
            y += dy[dir]

            ans = max(ans, x * x + y * y)
        }
    }

    return ans

}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

復(fù)雜度分析