題目資訊

題目編號: 353
題目連結: Design Snake Game
主題: Array, Hash Table, Design, Queue, Simulation

題目敘述

設計一個貪食蛇遊戲，這個遊戲是在螢幕尺寸為高 x 寬的設備上運行。如果你對這個遊戲不熟悉，可以在線上玩一玩。

貪食蛇最初位於左上角 $(0, 0)$，長度為 1 單位。

給定一個陣列 food，其中 food[i] = (r_i, c_i) 表示蛇可以吃到的一塊食物的行和列位置。當蛇吃掉一塊食物時，其長度和遊戲得分都會增加 1。

每塊食物依次出現在螢幕上，這意味著在蛇吃掉第一塊食物之前，第二塊食物不會出現。

當一塊食物出現在螢幕上時，保證它不會出現在被蛇佔據的區塊上。

如果蛇出界（撞到牆）或者其頭部移動後佔據了其身體佔據的空間（即長度為 4 的貪食蛇不能撞到自己），遊戲就會結束。

實作 SnakeGame 類別:

SnakeGame(int width, int height, int[][] food): 用大小為 height x width 的螢幕和食物的位置來初始化物件。
int move(String direction): 在應用蛇移動的一個方向後返回遊戲的分數。如果遊戲結束，返回 -1。

範例 1:

貪食蛇遊戲

輸入

["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]

輸出

[null, 0, 0, 1, 1, 2, -1]

說明

SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // 返回 0
snakeGame.move("D"); // 返回 0
snakeGame.move("R"); // 返回 1，蛇吃掉了第一塊食物。第二塊食物出現在 (0, 1)。
snakeGame.move("U"); // 返回 1
snakeGame.move("L"); // 返回 2，蛇吃掉了第二塊食物。不再有食物出現。
snakeGame.move("U"); // 返回 -1，遊戲結束因為蛇撞到邊界

限制條件：

$1 \leq \text{寬度}, \text{高度} \leq 10^4$
$1 \leq \text{food.length} \leq 50$
$\text{food}[i].\text{length} == 2$
$0 \leq r_i < \text{高度}$
$0 \leq c_i < \text{寬度}$
$\text{direction.length} == 1$
方向是 'U'、'D'、'L' 或 'R'。
最多會對 move 進行 $10^4$ 次呼叫。

直覺

本題目要求我們模擬經典的貪食蛇遊戲，其中蛇會在屏幕上移動，透過吃掉食物來成長，並且需避免與牆壁或自身發生碰撞。遊戲要求管理蛇的動態成長以及新食物的出現，並確保實時更新蛇的位置及其狀態（是活著還是死去）。限制條件強調了在查詢和更新蛇的位置時的效率。

解法

該解法利用了一個網格來表示遊戲屏幕，使用雙端佇列（deque）來有效地管理蛇的身體動態，並使用佇列（queue）順序管理食物項目。

初始化階段：
- 使用零值初始化一個網格以表示遊戲空間，當中 0 代表空位，1 代表蛇的部份，而 2 代表食物。
- 使用雙端佇列 snakeDeque 來存儲蛇的片段，頭部在前端。
- 使用一個佇列 foodQueue 初始化給定的食物位置，以便按出現順序追蹤剩餘的食物。
- 蛇的初始位置設定在網格的左上角 $(0, 0)$，並在網格上標記蛇的存在。
處理移動：
- 對於每次移動，根據指定的方向（‘U’、‘D’、‘L’、‘R’）更新蛇頭的位置，並計算出下一個位置。
- 邊界和自身碰撞檢查： 若新頭部位置越界或者進入自身的片段，遊戲結束且得分為 -1。
- 食物消耗： 若新頭部位置包含食物（網格值為 2），蛇的得分增加 1，且從網格上移除該食物項目。若還有更多的食物項目，下一個食物將會放置在網格上。
- 蛇的移動： 若下一個位置沒有食物，則移除蛇的尾部（以模擬移動），並從網格上清除其位置。
- 將蛇的新頭部位置加入至網格中（視為佔據）。
返回得分：
- 在處理完每次移動後，返回當前得分（可能因食物消耗進行過調整）。

此方法在每次移動中有效地維持更新和檢查，並利用雙端佇列的屬性來進行動態長度調整，以及使用佇列來順序訪問食物數據。

程式碼

C++

class SnakeGame {
private:
    // 網格
    // 0：空白區域
    // 1：蛇
    // 2：食物
    int width, height, score;
    vector<vector<int>> grid;
    deque<pair<int, int>> snakeDeque; // 雙端佇列用來保存蛇的節點（頭部在前）
    queue<pair<int, int>> foodQueue;  // 佇列用來保存食物的位置

public:
    // 建構子用於以指定的寬度、高度和食物位置初始化遊戲
    SnakeGame(int width, int height, vector<vector<int>>& food) {
        this->width = width;
        this->height = height;
        score = 0;
        grid.resize(height, vector<int>(width, 0)); // 初始化網格為全零

        // 將食物的初始位置載入佇列中
        for (vector<int>& f : food) {
            foodQueue.push({f[0], f[1]});
        }

        // 放置蛇的初始部分在網格中
        grid[0][0] = 1;
        snakeDeque.push_front({0, 0});

        // 放置第一個食物在網格中
        if (!foodQueue.empty()) {
            auto f = foodQueue.front();
            foodQueue.pop();
            grid[f.first][f.second] = 2;
        }
    }
    
    // 方法來移動蛇到指定方向
    int move(string direction) {
        // 根據當前的方向計算下一個位置
        auto currentPosition = snakeDeque.front();
        auto nextPosition = currentPosition;

        if (direction == "U") {
            nextPosition.first--;
        } else if (direction == "D") {
            nextPosition.first++;
        } else if (direction == "L") {
            nextPosition.second--;
        } else {
            nextPosition.second++;
        }

        // 檢查是否撞到牆
        if (nextPosition.first < 0 || nextPosition.first >= height ||
            nextPosition.second < 0 || nextPosition.second >= width) {
            return -1; // 遊戲結束
        }

        // 判斷蛇是否有找到食物
        bool foundFood = (grid[nextPosition.first][nextPosition.second] == 2);

        // 如果沒有找到食物，蛇向前移動：移除尾部節點
        if (!foundFood) {
            auto tail = snakeDeque.back();
            grid[tail.first][tail.second] = 0;
            snakeDeque.pop_back();
        }

        // 檢查是否自撞
        if (grid[nextPosition.first][nextPosition.second] == 1) {
            return -1; // 遊戲結束
        }

        // 在網格上放置新的頭部位置
        snakeDeque.push_front(nextPosition);
        grid[nextPosition.first][nextPosition.second] = 1;

        // 如果找到食物，增加分數並在有剩餘食物時放置新食物
        if (foundFood) {
            score++;
            if (!foodQueue.empty()) {
                auto newFoodPosition = foodQueue.front();
                foodQueue.pop();
                grid[newFoodPosition.first][newFoodPosition.second] = 2;
            }
        }

        return score; // 返回當前分數
    }
};

Python

from collections import deque
from queue import Queue

class SnakeGame:
    # 建構子初始化遊戲，給定寬度、高度和食物位置
    def __init__(self, width, height, food):
        self.width = width
        self.height = height
        self.score = 0
        self.grid = [[0] * width for _ in range(height)]  # 初始化網格為全零

        # 將初始食物位置加到隊列中
        self.foodQueue = Queue()
        for f in food:
            self.foodQueue.put((f[0], f[1]))

        # 將初始蛇的位置放置在網格上
        self.grid[0][0] = 1
        self.snakeDeque = deque([(0, 0)])

        # 將第一個食物放置在網格上
        if not self.foodQueue.empty():
            f = self.foodQueue.get()
            self.grid[f[0]][f[1]] = 2

    # 方法以給定的方向移動蛇
    def move(self, direction):
        # 根據當前方向計算下個位置
        currentPosition = self.snakeDeque[0]
        nextPosition = list(currentPosition)

        if direction == "U":
            nextPosition[0] -= 1
        elif direction == "D":
            nextPosition[0] += 1
        elif direction == "L":
            nextPosition[1] -= 1
        else:
            nextPosition[1] += 1

        # 檢查是否撞牆
        if nextPosition[0] < 0 or nextPosition[0] >= self.height or nextPosition[1] < 0 or nextPosition[1] >= self.width:
            return -1  # 遊戲結束

        # 判斷蛇是否找到食物
        foundFood = (self.grid[nextPosition[0]][nextPosition[1]] == 2)

        # 如果沒有找到食物，蛇向前移動：移除尾段
        if not foundFood:
            tail = self.snakeDeque.pop()
            self.grid[tail[0]][tail[1]] = 0

        # 檢查是否自撞
        if self.grid[nextPosition[0]][nextPosition[1]] == 1:
            return -1  # 遊戲結束

        # 將新頭部位置放置在網格上
        self.snakeDeque.appendleft(tuple(nextPosition))
        self.grid[nextPosition[0]][nextPosition[1]] = 1

        # 如果找到食物，增加分數並放置新食物（如果有的話）
        if foundFood:
            self.score += 1
            if not self.foodQueue.empty():
                newFoodPosition = self.foodQueue.get()
                self.grid[newFoodPosition[0]][newFoodPosition[1]] = 2

        return self.score  # 返回當前分數

複雜度分析

時間複雜度: $O(1)$
SnakeGame 類別中的 move 函數涉及基於方向更新蛇頭的位置、檢查碰撞以及可能更新食物位置。這些操作中的每一項——檢查網格碰撞、更新蛇的新位置的網格、處理被消耗的食物——均在固定時間內完成，即 $O(1)$，因為它們涉及對網格元素或蛇身體的固定操作，這些操作由 deque 高效管理。移動不依賴於網格的大小或食物的數量，因為它總是只檢查固定數量的位置。
空間複雜度: $O(w \cdot h)$
空間複雜度由網格的大小決定，該網格在記憶體中維持以標記蛇的位置和食物。網格的大小為 $w \cdot h$，其中 $w$ 是遊戲區域的寬度，而 $h$ 是高度。此外，一個雙端佇列被用來存儲蛇的段，最壞情況下，這些段可以存儲大多數的單元格，但仍受限於網格的大小。因此，主要的空間複雜度來自於網格本身，為 $O(w \cdot h)$。

CS Note
En

Leetcode 353. Design Snake Game

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析