874. Walking Robot Simulation

Walking Robot Simulation - LeetCodeLeetCode

說真的這題我覺得還蠻難的.....看了很久

參考了以下幾個, 優化成最後的解法

Logical Thinking with Clear Code - undefined - LeetCodeLeetCode

874. 模拟行走机器人 - 力扣（LeetCode）力扣 LeetCode

其中方向有{北，東，南，西}，初始化北方。

-2：向左90度, 對應的當前方嚮往左一個即(dir-1)%4，但是程序 -1%4 並不能得出 3 而是 -1，所以正確的表示是(dir+3)% 4。

-1：向右90度，對應的是方向轉向下一個方向，即(dir+1)%4，通過取模來使得在四個方向來回循環轉向。

下面是方向的表示法, 其實是一樣的

這題機器人是朝北的, 看程式裡的註解, 還有使用了編碼加速 set 的存取

為什麼要 nx, ny, 因為怕遇到障礙, 遇到障礙後是不能繼續走的, 所以這步可能不會算, 所以要先用變數暫存, 如果遇到障礙, x,y 就會維持原值

    int nx = x + directions[direction][0]; // new x value, because if it has obstacles, remain old x value
    int ny = y + directions[direction][1];

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

&& 

private static final int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

are the same way

x 0
y 1

x, y = 0, 1

/*
     W
  S -|- N
     E
  according to the question, the robot faces north

  general case:
  use directions[direction] to caculate x,y
  
  North, direction = 0, directions[direction] = {0, 1}
  East,  direction = 1, directions[direction] = {1, 0}
  South, direction = 2, directions[direction] = {0, -1}
  West,  direction = 3, directions[direction] = {-1, 0}
     
  time conplexity: O(n+k), space complexity:O(k), n is commands array size, k is obstacles array size
*/
class Solution {
    public static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // north, east, south, west
    
    public int robotSim(int[] commands, int[][] obstacles) {
        Set<Long> obsMap = new HashSet<>();
        for (int[] o : obstacles) {
            long code = encode(o[0], o[1]);
            obsMap.add(code); 
        }
        
        int x = 0;
        int y = 0;
        int direction = 0;
        int maxSquare = 0;
        
        for (int cmd : commands) {
            if (cmd == -2) { // turn left, then caculate the direction
               direction = (direction + 3) % 4; // (direction - 1) % 4 = -1 => so use (direction + 3)%4
            } else if (cmd == -1) { // turn right, then caculate the direction
               direction = (direction + 1) % 4; 
            } else {
                for (int step = 0; step < cmd; step++) {
                    int nx = x + directions[direction][0]; // new x value, because if it has obstacles, remain old x value
                    int ny = y + directions[direction][1];
                    
                    long code = encode(nx, ny);
                    if (!obsMap.contains(code)) { // no obstacles, caculate the max result
                        x = nx; // update new value
                        y = ny;
                        maxSquare = Math.max(maxSquare, x*x + y*y);
                    }
                }
            }
        }
        return maxSquare;
    }
    
    // encoding: access set fast!
    // enocde obstacles(x,y) to (((long)x + 300000) << 16) + (long)y + 30000
    private long encode(int x, int y) {
        return (((long)x + 300000) << 16) + (long)y + 30000;
    }
}