题解 | 贪吃蛇游戏

#include <bits/stdc++.h>
#include <string>
#include <unordered_set>
#include <utility>
using namespace std;
using ll = long long;

deque<pair<int, int>> snake;
unordered_set<string> paths;
int dx[] = {0, 0, 0, -1, 1}; // 占位 上 下 左 右
int dy[] = {0, 1, -1, 0, 0};

bool moveSnake(int dir) {
    // TODO: 请实现移动逻辑
    auto head = snake.back();
    int x = head.first + dx[dir];
    int y = head.second + dy[dir];

    // 检查是否撞到自己
    string s = to_string(x) + ',' + to_string(y);
    if (paths.count(s)) {
        return true;
    }

    // 移动蛇身
    auto tail = snake.front();
    snake.pop_front();
    snake.emplace_back(x, y);

    // 更新路径
    paths.erase(to_string(tail.first) + ',' + to_string(tail.second));
    paths.insert(s);
    return false;
}

bool eatSnake(int dir) {
    // TODO: 请实现吃果子生长逻辑
    auto head = snake.back();
    int x = head.first + dx[dir];
    int y = head.second + dy[dir];

    // 检查是否撞到自己
    string s = to_string(x) + ',' + to_string(y);
    if (paths.count(s)) {
        return true;
    }

    // 移动蛇身
    snake.emplace_back(x, y);

    // 更新路径
    paths.insert(s);
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    snake.clear();
    paths.clear();
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        snake.emplace_back(x, y);
        paths.insert(to_string(x) + ',' + to_string(y));
    }
    for (int i = 0; i < q; i++) {
        int op, dir;
        cin >> op >> dir;
        bool collision = (op == 1 ? moveSnake(dir) : eatSnake(dir));
        if (collision) {
            cout << -1 << '\n';
            return 0;
        } else {
            for (auto it = snake.rbegin(); it != snake.rend(); ++it) {
                cout << it->first << ' ' << it->second << '\n';
            }
        }
    }
    return 0;
}