題目

874. Walking Robot Simulation
難度: 中間偏易

題意

有一機器人在2D XY平面上行走。初始座標為[0, 0]，朝向北方。
給定一組整數陣列commands代表每步的動作；commands[i]為-1向右轉，-2向左轉，正整數代表向前走commands[i]個格子。
給定整數陣列的陣列obstacles[i][j]代表座標[i, j]上有障礙物。機器人移動的過程，若前方是障礙物則停下來!
求機器人移動過程中，距離原點最遠的歐基里德距離

方向

題目名稱就自稱模擬題了，如同昨天說的，模擬題都偏簡單，看著題目照著刻就會過了!
有幾個值得提的要點:

1. 由於每移動的點都要查詢是否為障礙物，這種重複查詢存不存在的題目類型，就要膝跳反射用哈希表(Hash Map)來解。
2. 可以先存好北、東、南、西四個方向的陣列。設定方向初始化為0，代表向北。若向右轉則初始方向+1，若向左轉則初始方向-1。可以發現方向必須保持在0~3之間，這時就可以用modulo法，向右方向先加一再取除四的模數；向左則等價於方向先加三再取除四的模數。

圖學科普:
歐基里德距離:勾股定理的距離(直線距離)
曼哈頓距離:座標軸上的絕對軸距總和(走棋盤狀的距離)

實作

class Solution
{
private:
    // {x, y}
    // North, East, South, West
    const vector<vector<int>> direction = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles)
    {
        set<pair<int, int>> obstacle_set;
        for (auto obstacle : obstacles)
        {
            obstacle_set.insert({ obstacle[0], obstacle[1] });
        }

        int max_d  = 0;
        int curr_x = 0, curr_y = 0;
        int curr_dir = 0;  // Initialize to North
        for (auto cmd : commands)
        {
            // Turn left
            if (cmd == -2)
            {
                curr_dir = (curr_dir + 3) % 4;
                continue;
            }

            // Turn right
            if (cmd == -1)
            {
                curr_dir = (curr_dir + 1) % 4;
                continue;
            }

            // Go forward
            for (int i = 0; i < cmd; i++)
            {
                int next_x = curr_x + direction[curr_dir][0];
                int next_y = curr_y + direction[curr_dir][1];
                // If next grid is an obstacle, stop
                if (obstacle_set.find({ next_x, next_y }) != obstacle_set.end())
                    break;

                // Update current position
                curr_y = next_y;
                curr_x = next_x;

                // Calculate Euclidean distance
                max_d = max(max_d, curr_x * curr_x + curr_y * curr_y);
            }
        }
        return max_d;
    }
};

分析

架設commands數量為M，obstacles數量為N
時間複雜度: O(M + N)，建立N長度的障礙物哈希表，在最多查詢M次
空間複雜度: O(N)，障礙物的哈希表

結果

秒殺

覆盤

這題其實花了半小時，因為想嘗試為座標做哈希表，但西加加不熟
如上述實作，std::set<>可以支援std::pair<int, int>作為鍵值。但這題我們其實不用關心鍵值的排序(Who Car?)
因此我想嘗試std::unordered_set<std::pair<int, int>>，結果是unordered_set不支援std::pair，要自行實作hash function。
實作如下:

struct pair_hash {
    template <class T1, class T2>
    size_t operator () (const pair<T1, T2>& p) const {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ (h2 << 1); // or use boost::hash_combine
    }
};

接著obstacle_set就可以替換成

unordered_set<pair<int, int>, pair_hash> obstacle_set;

真的是挖坑給自己跳r