AVAST中文官方网站,2046影院,777 影音先锋

機器人在一個無限大小的 XY 網格平面上行走，從點處開始出發，面向北方。該機器人可以接收以下三種類型的命令：

：向左轉度
：向右轉度
：向前移動個單位長度

在網格上有一些格子被視為障礙物。第 i 個障礙物位于網格點。

機器人無法走到障礙物上，它將會停留在障礙物的前一個網格方塊上，但仍然可以繼續嘗試進行該路線的其余部分。

返回從原點到機器人所有經過的路徑點（坐標為整數）的最大歐式距離的平方。（即，如果距離為，則返回）

注意：

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

示例 1:

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

輸出：25

解釋：機器人開始位于 (0, 0)：

向北移動 4 個單位，到達 (0, 4)
右轉
向東移動 3 個單位，到達 (3, 4) 距離原點最遠的是 (3, 4) ，距離為 32 + 42 = 25

示例 2：

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

輸出：65

解釋：機器人開始位于 (0, 0)：

向北移動 4 個單位，到達 (0, 4)
右轉
向東移動 1 個單位，然后被位于 (2, 4) 的障礙物阻擋，機器人停在 (1, 4)
左轉
向北走 4 個單位，到達 (1, 8) 距離原點最遠的是 (1, 8) ，距離為 12 + 82 = 65

提示：

題解思路

如示例2圖示：

代碼實現的難點在于方向的切換，這一類題目我們統一采用 「方向數組」 來處理。

我們定義當前方向為dir，可取值為 {0，1，2，3}；分別代表 {北，東，南，西}。見上圖。

那么當機器人遇到改變方向的命令時，我們直接修改dir的值即可：

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

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

方向為北(0)時：每次前進 x 不變，y 加一。
方向為東(1)時：每次前進 x 加一，y 不變。
方向為南(2)時：每次前進 x 不變，y 減一。
方向為西(3)時：每次前進 x 減一，y 不變。

代碼實現

Java

class Solution {

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

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

        genObstacleSet(obstacles);

        // 當前方向，北：0， 東：1，南：2， 西：3
        int dir = 0;

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

        // 機器人位置
        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++){
                // 如果遇到障礙物，停止在當前位置
                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 {

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

    // 當前方向
    dir := 0

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

    // 當前位置
    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
}