題目大意

經典貪吃蛇問題：在地圖中控制蛇移動，蛇身不可自撞、不可撞牆、不可進入障礙物。給定初始蛇身座標與障礙物，求蛇頭到達目標位置 (0,0) 的最小步數。蛇長固定，每步蛇頭移動一格，蛇尾收縮一格（除非吃到食物，本題無食物機制）。

核心難點

• 狀態空間極大：地圖最大 20×20，蛇長 ≤ 8，單純 BFS 狀態數可達 400×4⁷ ≈ 6.5 億，需極致壓縮。
• 狀態唯一標識：需將蛇身所有節點位置編碼為唯一整數，支援 O(1) 訪問判重。
• 移動合法性判定：新蛇頭不可越界、不可撞障礙、不可撞自身（除蛇尾同步移動外）。

狀態壓縮編碼策略

觀察：蛇身相鄰節點曼哈頓距離恆為 1，即方向僅有上下左右 4 種。以蛇頭座標 + 相對方向序列編碼：

• 蛇頭座標 (x, y)：各 5 bits（0~19），共 10 bits。
• 後續 L-1 段方向：每段 2 bits（0:上, 1:右, 2:下, 3:左），共 2*(L-1) bits。
• 最大 L=8 → 10 + 14 = 24 bits，完美置入 32 位整數。

編碼函數：

int encodeState(const Node& snake) {
    int code = snake.x * 20 + snake.y; // 頭部座標壓縮為 0~399
    for (int i = 1; i < snake.len; ++i) {
        int dir = getDirection(snake.p[i-1], snake.p[i]); // 上一節點→當前節點方向
        code = (code << 2) | dir;
    }
    return code;
}

BFS 核心邏輯

struct Node {
    uint8_t x, y;       // 蛇頭座標
    uint8_t len;        // 蛇長
    uint8_t dirs[7];    // 相對方向序列 (len-1)
    uint16_t step;      // 步數
};

int bfs() {
    std::queue<Node> q;
    std::vector<bool> visited(1 << 24, false); // 狀態訪問標記
    
    Node start = parseInput();
    int startCode = encodeState(start);
    visited[startCode] = true;
    q.push(start);

    const int dx[4] = {-1, 0, 1, 0};
    const int dy[4] = {0, 1, 0, -1};

    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.x == 0 && cur.y == 0) return cur.step; // 到達目標

        for (int d = 0; d < 4; ++d) {
            int nx = cur.x + dx[d], ny = cur.y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 越界
            if (obstacle[nx][ny]) continue; // 障礙物
            
            // 構造新狀態
            Node nxt = cur;
            nxt.x = nx; nxt.y = ny; nxt.step++;
            // 更新方向序列：新方向插入頭部，尾部捨棄
            for (int i = nxt.len - 1; i > 0; --i) nxt.dirs[i] = nxt.dirs[i-1];
            nxt.dirs[0] = opposite(d); // 新頭部相對舊頭部方向
            
            // 自身碰撞檢測（排除蛇尾同步移動的位置）
            if (selfCollision(nxt)) continue;

            int code = encodeState(nxt);
            if (!visited[code]) {
                visited[code] = true;
                q.push(nxt);
            }
        }
    }
    return -1; // 無解
}

自身碰撞檢測優化

利用方向序列還原蛇身所有座標，存入 bool body[20][20]，檢查新頭部是否落在蛇身上（蛇尾座標除外，因同步移動會騰空）。

bool selfCollision(const Node& s) {
    bool body[20][20] = {false};
    int x = s.x, y = s.y;
    body[x][y] = true; // 頭部
    for (int i = 0; i < s.len - 1; ++i) {
        x += dx[s.dirs[i]];
        y += dy[s.dirs[i]];
        if (i != s.len - 2) body[x][y] = true; // 蛇尾不標記
    }
    return body[s.x][s.y]; // 新頭部是否撞身體
}

複雜度分析

• 狀態數上限：400 × 4⁷ = 655,360,000，實際可達狀態遠小於此（牆壁、障礙、自身限制）。
• 時間複雜度：O(可達狀態數 × 4)，配合位運算編碼極快。
• 空間複雜度：visited 數組 16M bool ≈ 16 MB，隊列同級，符合限制。

關鍵優化技巧總結

完整 AC 代碼架構

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
const int MAX_STATE = 1 << 24;
const int MAXQ = 500000;

int n, m, L;
bool obstacle[MAXN][MAXN];
bool visited[MAX_STATE];
Node q[MAXQ];
int head, tail;

int main() {
    while (cin >> n >> m >> L) {
        if (n == 0 && m == 0 && L == 0) break;
        memset(obstacle, 0, sizeof(obstacle));
        memset(visited, 0, sizeof(visited));
        // 讀取障礙物、蛇身初始座標...
        cout << bfs() << endl;
    }
    return 0;
}

心得總結

本題是「狀態壓縮 BFS」教科書級範例。關鍵在於：

1. 發現拓撲結構的冗餘度（相鄰節點固定相對關係）
2. 設計最小完備編碼（頭座標 + 相對方向）
3. 正確處理邊界條件（蛇尾同步移動不算撞擊）
4. 工程化優化（位運算、靜態數組、循環隊列）

這類技巧廣泛應用於滑塊謎、推箱子、多實體移動等狀態空間搜索問題。