题目链接

贪吃蛇游戏

题目描述

你需要在一个全局的双端队列 snake 上实现贪吃蛇的移动和吃食物逻辑。该队列从头到尾（front to back）依次存放蛇尾到蛇头的坐标。

你需要实现两个函数：

  1. moveSnake(dir): 模拟蛇的移动。

    • 蛇头向 dir 方向移动一格。
    • 身体其他部分跟随移动（即蛇尾移动到之前邻近格子的位置）。
    • 如果移动后蛇头与身体其他部分重叠，则视为碰撞，不执行移动并返回 true。否则，执行移动并返回 false。

  2. eatSnake(dir): 模拟蛇吃食物。

    • 蛇头向 dir 方向移动一格。
    • 身体其他部分不移动（即蛇尾留在原地），从而实现身体变长。
    • 如果移动后蛇头与整个身体重叠，则视为碰撞，不执行移动并返回 true。否则，执行移动并返回 false。

方向 dir 定义:

  • 1: 上 (y+1)
  • 2: 下 (y-1)
  • 3: 左 (x-1)
  • 4: 右 (x+1)

这是一个 核心代码模式 的题目，你只需要补全 moveSnake 和 eatSnake 函数。

解题思路

本题的核心是正确地使用双端队列（Deque）来维护蛇的身体坐标，并根据不同操作（移动、吃）更新队列。

数据结构约定:

  • 我们使用一个全局的 deque。
  • snake.front(): 蛇尾坐标。
  • snake.back(): 蛇头坐标。

moveSnake(dir) 逻辑详解:

  1. 计算新蛇头位置: 获取当前蛇头 snake.back() 的坐标 (x, y)，根据方向 dir 计算出新蛇头 new_head 的坐标。
  2. 碰撞检测:
    • 关键点：移动时，旧的蛇头会空出位置，所以新蛇头不能与移动前的除蛇头外的任何身体部分重叠。
    • 我们需要遍历 snake 中除了最后一个元素（旧蛇头）之外的所有部分，检查 new_head 是否与其中任何一个坐标相同。
  3. 执行移动:
    • 如果检测到碰撞，立即返回 true，不修改 snake。
    • 如果没有碰撞，执行移动：
      • 在队头移除蛇尾：snake.pop_front()。
      • 在队尾添加新蛇头：snake.push_back(new_head)。
      • 返回 false。

eatSnake(dir) 逻辑详解:

  1. 计算新蛇头位置: 同上。
  2. 碰撞检测:
    • 关键点：吃食物时，蛇身会变长，旧的蛇头变成了身体的一部分。因此，新蛇头不能与移动前的整个身体（包括旧蛇头）的任何部分重叠。
    • 我们需要遍历 snake 中所有的部分，检查 new_head 是否与其中任何一个坐标相同。
  3. 执行移动和生长:
    • 如果检测到碰撞，立即返回 true，不修改 snake。
    • 如果没有碰撞，执行生长：
      • 不移除蛇尾。
      • 在队尾添加新蛇头：snake.push_back(new_head)。
      • 返回 false。

代码

bool moveSnake(int dir) {
    pair<int, int> head = snake.back();
    pair<int, int> new_head = head;

    if (dir == 1) new_head.second++;
    else if (dir == 2) new_head.second--;
    else if (dir == 3) new_head.first--;
    else if (dir == 4) new_head.first++;

    // 碰撞检测：检查除尾部以外的身体部分
    for (auto it = snake.begin(); it != prev(snake.end()); ++it) {
        if (*it == new_head) {
            return true; // 发生碰撞
        }
    }

    snake.pop_front();
    snake.push_back(new_head);
    return false;
}

bool eatSnake(int dir) {
    pair<int, int> head = snake.back();
    pair<int, int> new_head = head;

    if (dir == 1) new_head.second++;
    else if (dir == 2) new_head.second--;
    else if (dir == 3) new_head.first--;
    else if (dir == 4) new_head.first++;

    // 碰撞检测：检查整个身体
    for (const auto& segment : snake) {
        if (segment == new_head) {
            return true; // 发生碰撞
        }
    }

    snake.push_back(new_head);
    return false;
}

public static boolean moveSnake(int dir) {
    int[] head = snake.getLast();
    int[] new_head = new int[]{head[0], head[1]};

    if (dir == 1) new_head[1]++;
    else if (dir == 2) new_head[1]--;
    else if (dir == 3) new_head[0]--;
    else if (dir == 4) new_head[0]++;

    // 碰撞检测：检查除尾部以外的身体部分
    Iterator<int[]> it = snake.iterator();
    while (it.hasNext()) {
        int[] segment = it.next();
        if (!it.hasNext()) { // 到达最后一个元素（蛇头），跳出
            break;
        }
        if (Arrays.equals(segment, new_head)) {
            return true; // 发生碰撞
        }
    }

    snake.removeFirst();
    snake.addLast(new_head);
    return false;
}

public static boolean eatSnake(int dir) {
    int[] head = snake.getLast();
    int[] new_head = new int[]{head[0], head[1]};

    if (dir == 1) new_head[1]++;
    else if (dir == 2) new_head[1]--;
    else if (dir == 3) new_head[0]--;
    else if (dir == 4) new_head[0]++;

    // 碰撞检测：检查整个身体
    for (int[] segment : snake) {
        if (Arrays.equals(segment, new_head)) {
            return true; // 发生碰撞
        }
    }

    snake.addLast(new_head);
    return false;
}

def moveSnake(dir):
    global snake
    head_x, head_y = snake[-1]
    
    if dir == 1: new_head = (head_x, head_y + 1)
    elif dir == 2: new_head = (head_x, head_y - 1)
    elif dir == 3: new_head = (head_x - 1, head_y)
    else: new_head = (head_x + 1, head_y)

    # 碰撞检测：检查除尾部以外的身体部分
    # 创建一个不包含最后一个元素的迭代器进行检查
    import itertools
    for segment in itertools.islice(snake, 0, len(snake) - 1):
        if segment == new_head:
            return True # 发生碰撞

    snake.popleft()
    snake.append(new_head)
    return False

def eatSnake(dir):
    global snake
    head_x, head_y = snake[-1]

    if dir == 1: new_head = (head_x, head_y + 1)
    elif dir == 2: new_head = (head_x, head_y - 1)
    elif dir == 3: new_head = (head_x - 1, head_y)
    else: new_head = (head_x + 1, head_y)

    # 碰撞检测：检查整个身体
    if new_head in snake:
        return True # 发生碰撞

    snake.append(new_head)
    return False

算法及复杂度

  • 算法: 模拟 + 双端队列
  • 时间复杂度: ，对于每次操作，都需要遍历一次蛇的身体（长度为 ）来进行碰撞检测。因此，对于 Q 次操作，总复杂度为 。
  • 空间复杂度: ，即蛇能达到的最大长度。空间用于存储蛇身的坐标。