Archives/walking_robot_simulation.cpp at master · shafitek/Archives · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// https://leetcode.com/problems/walking-robot-simulation/

class Solution
{
public:
    int robotSim(vector<int> &commands, vector<vector<int>> &obstacles)
    {
        enum Direction
        {
            NEG_X = 1,
            NEG_Y = 3,
            POS_X = 4,
            POS_Y = 2
        };
        Direction dir = POS_Y;
        set<int> obs_set;
        int x = 0, y = 0;
        short pos_neg = 1;
        int amt_to_inc = 0;
        int max_dist = 0;

        for (auto const &obs : obstacles)
            obs_set.insert(hash(obs[0], obs[1]));

        for (auto const &c : commands)
        {
            if (c == -2)
            {
                if (dir == POS_Y)
                    dir = NEG_X;
                else if (dir == NEG_X)
                    dir = NEG_Y;
                else if (dir == NEG_Y)
                    dir = POS_X;
                else if (dir == POS_X)
                    dir = POS_Y;
            }
            if (c == -1)
            {
                if (dir == POS_X)
                    dir = NEG_Y;
                else if (dir == NEG_Y)
                    dir = NEG_X;
                else if (dir == NEG_X)
                    dir = POS_Y;
                else if (dir == POS_Y)
                    dir = POS_X;
            }
            if (c > 0)
            {
                pos_neg = (dir % 2) ? -1 : 1;
                for (int s = 0; s < c; s++)
                {
                    if (dir == POS_X || dir == NEG_X)
                    {
                        amt_to_inc = x + pos_neg;
                        if (obs_set.count(hash(amt_to_inc, y)) > 0)
                            break;
                        x = amt_to_inc;
                    }
                    if (dir == POS_Y || dir == NEG_Y)
                    {
                        amt_to_inc = y + pos_neg;
                        if (obs_set.count(hash(x, amt_to_inc)) > 0)
                            break;
                        y = amt_to_inc;
                    }
                }
            }
            max_dist = std::max(x * x + y * y, max_dist);
        }

        return max_dist;
    }

    static uint32_t hash(int x, int y)
    {
        return ((uint32_t)(x + 30000) << 16) + (y + 30000);
    }
};