题解：七彩贪吃蛇

问题分析

本题需要模拟一条贪吃蛇在棋盘上的移动、吃零食并响应颜色查询的过程。核心要点包括：

1. 蛇的初始状态：长度为1，头部在(1,1)，颜色为0。
2. 移动规则：蛇头移动后，身体依次跟随；吃到零食时蛇身变长，头部颜色为零食颜色。
3. 查询需求：实时特定时刻指定格子上蛇的颜色（若存在）。

关键思路

1. 时间戳记录位置：用二维数组 t[x][y] 记录蛇头到达 (x,y) 的时间（操作次数）。蛇的身体部分会在后续时间依次占据前一位置，因此某格子 (x,y) 上的蛇身存在时间为 [t[x][y], t[x][y] + 蛇长 - 1]。

2. 蛇身颜色存储：用数组 snake[] 按时间顺序存储蛇头的颜色（包括初始颜色和吃到的零食颜色）。蛇身第 i 段（从尾到头）的颜色对应 snake[i]。

3. 零食管理：用二维数组 check[x][y] 存储零食颜色（+1 区分无零食的0值），吃到后清空。

4. 查询处理：对于查询 (x,y)，若当前时间 now 与格子时间戳 t[x][y] 的差值在蛇长范围内，则通过 snake 数组计算对应颜色；否则输出-1。

代码解析

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

int m, p, n;
int check[2001][2001];  // 存储零食颜色（+1避免与0混淆）
int t[2001][2001];      // 记录蛇头到达(x,y)的时间戳
int snake[1000001];     // 存储蛇头颜色（按时间顺序）
int l = 1;              // 蛇当前长度
int nowx = 1, nowy = 1; // 蛇头当前位置
int now = 1;            // 当前时间（操作次数）

int main() {
    cin >> m >> p >> n;
    t[1][1] = 1;         // 初始位置时间戳为1
    snake[1] = 0;        // 初始蛇头颜色为0

    // 读取零食位置和颜色
    while (p--) {
        int x, y, v;
        cin >> x >> y >> v;
        check[x][y] = v + 1;  // +1区分无零食的0
    }

    // 处理每条指令
    while (n--) {
        char a;
        cin >> a;

        if (a == 'Z') {  // 查询操作
            int x, y;
            cin >> x >> y;
            // 计算格子(x,y)上蛇身的存在性
            if (t[x][y] == 0) {  // 蛇从未经过此格
                cout << "-1\n";
            } else {
                int len = now - t[x][y] + 1;  // 理论长度
                if (len > l) {  // 蛇已离开此格
                    cout << "-1\n";
                } else {  // 计算对应颜色
                    cout << snake[l - (now - t[x][y])] << "\n";
                }
            }
        } else {  // 移动操作
            now++;  // 时间递增
            // 更新蛇头位置
            if (a == 'G') nowx--;
            if (a == 'D') nowx++;
            if (a == 'L') nowy--;
            if (a == 'P') nowy++;

            t[nowx][nowy] = now;  // 记录新位置的时间戳

            // 检查是否吃到零食
            if (check[nowx][nowy]) {
                l++;  // 蛇身变长
                snake[l] = check[nowx][nowy] - 1;  // 零食颜色（恢复-1）
                check[nowx][nowy] = 0;  // 清空零食
            }
        }
    }

    return 0;
}

复杂度分析

• 时间复杂度：每个指令（移动或查询）处理时间为 O(1)，总复杂度为 O(n + p)，可应对 1e6 级别的输入。
• 空间复杂度：数组 check 和 t 大小为 O(m²)（m≤2000，约4e6），snake 数组大小为 O(n)（1e6），空间足够。

该解法通过时间戳和颜色数组高效模拟蛇的移动和生长，同时快速响应查询，完美适配题目需求。