ปูพื้นฐาน

กราฟที่โจทย์ไม่ได้ให้มา: แปลงคำว่า "อย่างน้อยกี่ท่า" เป็นโค้ดชุดเดิมทุกครั้ง

เหยือกน้ำ ล็อกรหัส กระดานเลื่อนเบี้ย ใช้โค้ดชุดเดียวกันหมด ของที่ต้องเตรียมไปคือสามคำถามที่ต้องตอบให้ได้ก่อนพิมพ์โค้ดทุกครั้ง และสัญญาณที่บอกว่าเมื่อไรกราฟใหญ่เกินกว่าจะเดินตรง ๆ พร้อมโจทย์ฝึก 3 ข้อ

อาการ · โจทย์ที่ถามว่า "อย่างน้อยกี่ท่า" แต่ไม่มีกราฟมาให้

โจทย์กลุ่มนี้หน้าตาไม่เหมือนโจทย์กราฟเลยสักนิด มีเหยือกน้ำสองใบ ตวงให้ได้สี่ลิตรพอดีต้องทำอย่างน้อยกี่ท่า มีล็อกรหัสสี่หลัก หมุนจาก 0000 ไปเป็นรหัสหนึ่งโดยห้ามผ่านรหัสต้องห้าม ทำได้ไหมและกี่ครั้ง มีกระดานเลื่อนเบี้ย จัดให้เข้าที่ต้องเลื่อนกี่ตา

ทั้งหมดนี้เป็นโจทย์เดียวกัน และมันเป็นโจทย์กราฟที่เราต้องสร้างกราฟขึ้นมาเอง ความยากไม่ได้อยู่ที่อัลกอริทึม เพราะอัลกอริทึมคือการค้นตามความกว้างธรรมดาที่เขียนสิบบรรทัดจบ ความยากอยู่ที่การมองให้ออกว่าอะไรคือจุด และอะไรคือเส้น

สองคำที่ต้องนิยามให้ได้ก่อนเขียนโค้ด

สถานะ (state) คือภาพนิ่งของโลกที่มีข้อมูลพอจะเดินต่อได้โดยไม่ต้องรู้อดีต ในโจทย์เหยือกน้ำ สถานะคือปริมาณน้ำในเหยือกทั้งสองใบ ไม่ต้องรู้เลยว่ากว่าจะมาถึงตรงนี้เททิ้งไปกี่รอบ เพราะสิ่งที่ทำได้ต่อจากนี้ขึ้นกับปริมาณน้ำตอนนี้เท่านั้น

เส้นเชื่อมคือหนึ่งท่าที่กติกาอนุญาต ในโจทย์เหยือกน้ำมีหกท่าคือเติมใบใดใบหนึ่งให้เต็ม เททิ้งใบใดใบหนึ่ง และเทใบหนึ่งใส่อีกใบจนกว่าใบรับจะเต็มหรือใบเทจะหมด

เมื่อทุกท่าราคาเท่ากันคือหนึ่งท่า การหาทางที่สั้นที่สุดจึงเป็นงานของการค้นตามความกว้าง (breadth-first search หรือ BFS) ซึ่งกวาดสถานะออกไปเป็นชั้น ๆ ชั้นที่ d คือสถานะทุกอันที่ไปถึงได้ ด้วย d ท่าพอดี ไม่มากไม่น้อยกว่านั้น

ชั้นแรกที่มีสถานะที่เราต้องการคือชั้นที่ 6 คำตอบของโจทย์นี้จึงเป็น 6 ท่า และเพราะเราเดินเป็นชั้น เราจึงรู้ทันทีว่าไม่มีทางที่สั้นกว่านี้ ไม่ต้องพิสูจน์อะไรเพิ่ม

โครงที่ใช้ซ้ำได้ทุกข้อ

เมื่อนิยามสถานะกับเส้นเชื่อมได้แล้ว โค้ดที่เหลือเหมือนกันหมดทุกข้อ เปลี่ยนแค่สามจุด

// โครงของการค้นตามความกว้าง ใช้ซ้ำได้ทุกข้อ เปลี่ยนแค่สามจุดที่มีคอมเมนต์กำกับ
vector<int> dist(STATES, -1);          // (1) จำนวนสถานะทั้งหมด
queue<int> q;

dist[START] = 0;                       // (2) สถานะเริ่มต้น
q.push(START);

while (!q.empty()) {
    int v = q.front(); q.pop();
    if (isGoal(v)) { answer = dist[v]; break; }

    for (int u : neighbours(v)) {      // (3) หนึ่งท่าที่ทำได้จากสถานะ v
        if (dist[u] != -1) continue;   // เคยไปถึงแล้วด้วยระยะที่สั้นกว่าหรือเท่ากัน
        dist[u] = dist[v] + 1;
        q.push(u);
    }
}

จุดที่เหลือให้คิดจริง ๆ มีข้อเดียว คือจะเข้ารหัสสถานะเป็นเลขตัวเดียวยังไง เพราะเราอยากใช้อาเรย์ธรรมดาเป็นตัวจำว่าไปถึงหรือยัง ไม่ใช่ตารางแฮชที่ช้ากว่าหลายเท่า ในโจทย์เหยือกน้ำ สถานะ (a, b) อัดเป็น a × (Y + 1) + b ได้ตรง ๆ เหมือนการอ่านเลขสองหลักในฐาน Y + 1

ลองเอง · ตวงน้ำให้ได้พอดี

ลองนับดูว่าสถานะที่ต่างกันจริง ๆ มีกี่แบบ แล้วเทียบกับจำนวนลำดับท่าที่เป็นไปได้ ซึ่งโตแบบทวีคูณ

โจทย์ฝึก · ไล่จากง่ายไปยาก

สามข้อนี้ตอบคนละคำถาม ข้อแรกถามว่า "สถานะที่เห็นชัดอยู่แล้วเขียนยังไง" ข้อสองถามว่า "ถ้าสถานะไม่ใช่ตำแหน่งบนแผนที่" ข้อสามถามว่า "ถ้าบางสถานะเข้าไม่ได้เลย" ลองคิดเองก่อนแล้วค่อยแตะดูเฉลยครับ

ฝึกข้อ 1 ★☆☆☆☆ · เดินออกจากเขาวงกต

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

int main() {
    int R, C;
    scanf("%d %d", &R, &C);
    vector<string> g(R);
    for (auto& s : g) { char b[1024]; scanf("%s", b); s = b; }

    int sr = 0, sc = 0, tr = 0, tc = 0;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            if (g[i][j] == 'S') { sr = i; sc = j; }
            if (g[i][j] == 'T') { tr = i; tc = j; }
        }

    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int, int>> q;
    dist[sr][sc] = 0;
    q.push({sr, sc});

    const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
            if (g[nx][ny] == '#') continue;
            if (dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
    printf("%d\n", dist[tr][tc]);   // ไปไม่ถึงจะยังเป็น -1 อยู่พอดี
    return 0;
}

ฝึกข้อ 2 ★★☆☆☆ · เหยือกน้ำสองใบ

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

int main() {
    int X, Y, Z;
    scanf("%d %d %d", &X, &Y, &Z);

    // สถานะคือ (a, b) ปริมาณน้ำในใบเล็กและใบใหญ่ อัดเป็นเลขตัวเดียว a*(Y+1)+b
    int S = (X + 1) * (Y + 1);
    vector<int> dist(S, -1);
    auto id = [&](int a, int b) { return a * (Y + 1) + b; };

    queue<int> q;
    dist[id(0, 0)] = 0;
    q.push(id(0, 0));

    int ans = -1;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        int a = cur / (Y + 1), b = cur % (Y + 1);
        if (a == Z || b == Z) { ans = dist[cur]; break; }

        int t  = min(a, Y - b);        // เทใบเล็กใส่ใบใหญ่ ได้เท่าที่ใบใหญ่ยังว่าง
        int t2 = min(b, X - a);        // เทใบใหญ่ใส่ใบเล็ก
        int nx[6][2] = {{X, b}, {a, Y}, {0, b}, {a, 0}, {a - t, b + t}, {a + t2, b - t2}};

        for (auto& p : nx) {
            int j = id(p[0], p[1]);
            if (dist[j] == -1) { dist[j] = dist[cur] + 1; q.push(j); }
        }
    }
    printf("%d\n", ans);
    return 0;
}

ฝึกข้อ 3 ★★★☆☆ · ล็อกรหัสที่มีรหัสต้องห้าม

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

int main() {
    char tgt[16];
    int m;
    scanf("%s %d", tgt, &m);

    vector<char> bad(10000, 0);
    for (int i = 0; i < m; i++) { char s[16]; scanf("%s", s); bad[atoi(s)] = 1; }
    int target = atoi(tgt);

    if (bad[0]) { printf("-1\n"); return 0; }   // ออกจากจุดเริ่มไม่ได้เลย

    vector<int> dist(10000, -1);
    queue<int> q;
    dist[0] = 0;
    q.push(0);

    while (!q.empty()) {
        int v = q.front(); q.pop();
        if (v == target) break;

        int p[4] = {1000, 100, 10, 1};
        for (int k = 0; k < 4; k++) {
            int digit = (v / p[k]) % 10;
            for (int d : {1, 9}) {                 // หมุนขึ้นหนึ่ง กับหมุนลงหนึ่ง (คือขึ้นเก้าแบบวน)
                int nd = (digit + d) % 10;
                int u = v + (nd - digit) * p[k];
                if (bad[u] || dist[u] != -1) continue;
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
    printf("%d\n", dist[target]);
    return 0;
}

เส้นแบ่งที่ต้องรู้ · BFS ธรรมดาพังเมื่อไร แล้วต้องใช้อะไรแทน

ทั้งบทนี้ยืนอยู่บนสมมติฐานเงียบ ๆ ข้อหนึ่ง คือทุกท่ามีราคาเท่ากันคือหนึ่ง สมมติฐานนั้นคือเหตุผลเดียวที่ BFS ใช้ได้ เพราะเมื่อทุกก้าวราคาเท่ากัน ลำดับที่เราไปเจอสถานะจึงเรียงตามระยะทางพอดี คิวจึงไม่มีวันเสียลำดับ

พอโจทย์เปลี่ยนให้บางท่าราคาต่างกัน สมมติฐานนั้นหายไป และ BFS จะให้คำตอบผิดแบบเงียบ ๆ ไม่ใช่พังหรือวนไม่จบ มันจะตอบเลขที่น้อยกว่าความจริง เพราะมันไปถึงสถานะหนึ่งด้วยเส้นทางที่ ก้าวน้อยแต่แพงกว่า แล้วปิดตายสถานะนั้นไปเลย ทั้งที่มีเส้นทางที่ก้าวมากกว่าแต่ถูกกว่ารออยู่ นี่คือบั๊กประเภทที่ตัวอย่างในโจทย์มักจับไม่ได้

กรณีที่เจอบ่อยที่สุดคือราคามีแค่สองแบบ คือ 0 กับ 1 เช่นโจทย์ที่เดินในทิศเดิมฟรี แต่เลี้ยวเสียหนึ่งครั้ง หรือผ่านช่องว่างฟรีแต่ทุบกำแพงเสียหนึ่ง กรณีนี้ไม่ต้องขยับไปใช้ Dijkstra ที่มีคิวลำดับความสำคัญและ log ติดมาด้วย มีท่าที่แก้ด้วยการเปลี่ยนคิวเป็น แถวสองหัว เท่านั้น เรียกว่า 0-1 BFS

กฎมีบรรทัดเดียว เมื่อผ่อนคลายเส้นที่ราคา 0 ให้ใส่ปมปลายทางไว้ที่หัวแถว เมื่อผ่อนคลายเส้นที่ราคา 1 ให้ใส่ไว้ที่ท้ายแถว เหตุผลตรงไปตรงมา เส้นราคา 0 ไม่เพิ่มระยะเลย ปมปลายทางจึงต้องอยู่ในชั้นเดียวกับปมที่เรากำลังยืน มันจึงต้องได้คิวก่อนทุกปมที่อยู่ชั้นถัดไป และเส้นราคา 1 พาไปชั้นถัดไปพอดี จึงต่อท้ายเหมือน BFS เดิม ผลคือแถวยังเรียงตามระยะทางเสมอ เหมือนที่คิวเคยเรียงให้ตอนทุกก้าวราคาเท่ากัน

// 0-1 BFS: ระยะทางสั้นสุดเมื่อเส้นเชื่อมมีน้ำหนักได้แค่ 0 หรือ 1
// ใช้แถวสองหัว เส้นน้ำหนัก 0 ใส่หัวแถว เส้นน้ำหนัก 1 ใส่ท้ายแถว
// อินพุต: n m start แล้ว m บรรทัด u v w  (กราฟไม่มีทิศ, w เป็น 0 หรือ 1)
// เอาต์พุต: ระยะจาก start ถึงทุกปม ปมที่ไปไม่ถึงพิมพ์ -1
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, start;
    if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    const int INF = INT_MAX;
    vector<int> dist(n, INF);
    deque<int> dq;
    dist[start] = 0;
    dq.push_back(start);
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        for (auto [v, w] : g[u]) {
            // ถ้าเส้นนี้ไม่เพิ่มระยะเลย ปมปลายทางต้องได้คิวเท่ากับปมนี้ จึงต้องอยู่หัวแถว
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
    for (int i = 0; i < n; i++) printf("%d%c", dist[i] == INF ? -1 : dist[i], i + 1 == n ? '\n' : ' ');
    return 0;
}

// ตัวตรวจอิสระของ 0-1 BFS: Bellman-Ford แบบผ่อนคลายซ้ำจนไม่มีอะไรเปลี่ยน
// ไม่รู้จักแถวสองหัว ไม่รู้จักลำดับคิว จึงไม่ได้ทดสอบข้ออ้างเรื่องหัวแถวท้ายแถวเลย
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, start;
    if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
    vector<array<int, 3>> e(m);
    for (int i = 0; i < m; i++) scanf("%d %d %d", &e[i][0], &e[i][1], &e[i][2]);
    const int INF = INT_MAX;
    vector<int> dist(n, INF);
    dist[start] = 0;
    for (int it = 0; it < n; it++) {
        bool changed = false;
        for (auto& x : e) {
            int u = x[0], v = x[1], w = x[2];
            if (dist[u] != INF && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; changed = true; }
            if (dist[v] != INF && dist[v] + w < dist[u]) { dist[u] = dist[v] + w; changed = true; }
        }
        if (!changed) break;
    }
    for (int i = 0; i < n; i++) printf("%d%c", dist[i] == INF ? -1 : dist[i], i + 1 == n ? '\n' : ' ');
    return 0;
}

เกณฑ์เลือกจึงเรียงได้เป็นบันได ราคาเท่ากันหมดให้ใช้ BFS ราคาเป็น 0 กับ 1 ให้ใช้ 0-1 BFS ราคาเป็นจำนวนเต็มเล็ก ๆ หลายค่าให้ใช้คิวหลายชั้น และราคาเป็นอะไรก็ได้ให้ใช้ Dijkstra สิ่งที่ต้องจำคืออย่าใช้ BFS กับกราฟที่ราคาไม่เท่ากัน เพราะมันไม่เตือนอะไรเลย

สรุปบรรทัดเดียว

ถ้าโจทย์ถามว่า "อย่างน้อยกี่ท่า" และทุกท่าราคาเท่ากัน ให้หยุดคิดเรื่องอัลกอริทึมทันที แล้วไปตอบสองคำถามแทน ว่าสถานะคืออะไรกับท่าหนึ่งท่าพาไปไหนได้บ้าง ที่เหลือคือโครงสิบบรรทัดที่เหมือนกันทุกข้อ และถ้านับสถานะแล้วได้ตัวเลขที่ใหญ่เกินสร้างอาเรย์ นั่นไม่ใช่สัญญาณว่าต้องหาอัลกอริทึมที่แรงกว่า แต่เป็นสัญญาณว่าอ่านโจทย์ยังไม่ครบ