Deque + unordered_set (c++)


  • 0
    C

    //use unordered_set to fast check if a grid is occupied by the snake

    //use deque to fast query the head and the tail

    //the new position of the head can be updated fast using deque and input direction, then check the new possition against the following conditions:

    // 1. out of boundaries or intersect with body(except the tail)

    // 2. get food

    // 3. other than above 2 cases

    set<pair<int, int>> body_s;
    deque<pair<int, int>> body_q;
    int w;
    int h;
    vector<pair<int, int>> food_v;
    int food_id;
    unordered_map<string, pair<int, int>> m;
    
    SnakeGame(int width, int height, vector<pair<int, int>> food) {
        w = width;
        h = height;
        food_v = food;
        food_id = 0;
        body_q.push_back(make_pair<int, int>(0, 0));
        body_s.insert(make_pair<int, int>(0, 0));
        
        m["U"] = make_pair<int,int>(0,-1);
        m["D"] = make_pair<int,int>(0,1);
        m["L"] = make_pair<int,int>(-1,0);
        m["R"] = make_pair<int,int>(1,0);
    }
    
    int move(string direction) {
        auto p = m[direction];
        auto head = body_q.front();
        pair<int, int> new_pos = make_pair<int, int>(head.first + p.first, head.second + p.second);
        int new_posx = new_pos.first;
        int new_posy = new_pos.second;
        if(new_posx == -1 || new_posy == -1 || new_posx == w || new_posy == h || (body_s.find(new_pos) != body_s.end() && new_pos != body_q.back()))
                return -1;
            
        if(food_id != food_v.size() && new_posx == food_v[food_id].second && new_posy == food_v[food_id].first)
            food_id++;
        else
        {
           pair<int, int> tail = body_q.back();
           body_s.erase(tail);
           body_q.pop_back();
        }
        body_s.insert(new_pos);
        body_q.push_front(new_pos);
        return body_s.size() - 1;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.