27.5 BFS บนสถานะ และ 0-1 BFS

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

สถานะคือจุดยอด

กราฟของสถานะไม่ได้ให้มาเป็นรายการเส้นเชื่อม และไม่ต้องสร้างขึ้นมาก่อน เหมือนตารางในหน้า 27.4 ที่คำนวณเพื่อนบ้านด้วย dr กับ dc ทุกครั้ง สถานะก็คำนวณสถานะถัดไปจากการกระทำแต่ละแบบทุกครั้งที่หยิบออกจาก queue สิ่งที่ต้องเตรียมคือสามข้อเดียวกับหน้า 21.5

1. สถานะเก็บเป็นอะไร ถ้าแปลงเป็นเลขช่องของอาเรย์ได้ ใช้อาเรย์เก็บระยะ ถ้าไม่ได้ ใช้ map
2. จากสถานะหนึ่งไปสถานะไหนได้บ้าง
3. มีสถานะทั้งหมดกี่แบบ ตัวเลขนี้คูณจำนวนการกระทำต่อสถานะคือเวลาของ BFS

ตวงน้ำด้วยสองขวด

มีขวดเปล่าสองใบที่ไม่มีขีดบอกปริมาตร ขวด A จุ A ลิตร ขวด B จุ B ลิตร มีก๊อกน้ำกับอ่างให้เททิ้ง ทำได้หกอย่าง เติมขวดใดขวดหนึ่งจนเต็ม เททิ้งขวดใดขวดหนึ่งจนหมด หรือเทขวดหนึ่งใส่อีกขวดจนต้นทางหมดหรือปลายทางเต็ม อยากได้น้ำ T ลิตรพอดีในขวดใบใดใบหนึ่ง ต้องทำอย่างน้อยกี่ครั้ง

สถานะคือน้ำในสองขวด (a, b) มีได้ (A + 1)(B + 1) แบบ เก็บระยะในตาราง dist[a][b] ได้ตรงๆ แบบตารางในหน้า 27.4 และจด came_from กับ came_by ไว้พิมพ์ขั้นตอน

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

const string action_name[6] = {"fill A", "fill B", "empty A", "empty B", "pour A into B", "pour B into A"};
int cap_a, cap_b;

pair<int, int> apply_action(int a, int b, int action)
{
    if (action == 0) {
        return {cap_a, b}; // (1)!
    }
    if (action == 1) {
        return {a, cap_b};
    }
    if (action == 2) {
        return {0, b};
    }
    if (action == 3) {
        return {a, 0};
    }
    if (action == 4) {
        int moved = min(a, cap_b - b); // (2)!
        return {a - moved, b + moved};
    }
    int moved = min(b, cap_a - a);
    return {a + moved, b - moved};
}

int main()
{
    int target;
    cin >> cap_a >> cap_b >> target;
    vector<vector<int>> dist(cap_a + 1, vector<int>(cap_b + 1, -1)); // (3)!
    vector<vector<pair<int, int>>> came_from(cap_a + 1, vector<pair<int, int>>(cap_b + 1));
    vector<vector<int>> came_by(cap_a + 1, vector<int>(cap_b + 1, -1));
    queue<pair<int, int>> waiting;
    dist[0][0] = 0;
    waiting.push({0, 0});
    int end_a = -1, end_b = -1;
    while (!waiting.empty()) {
        auto [a, b] = waiting.front();
        waiting.pop();
        if (a == target || b == target) { // (4)!
            end_a = a;
            end_b = b;
            break;
        }
        for (int action = 0; action < 6; action++) {
            auto [na, nb] = apply_action(a, b, action);
            if (dist[na][nb] == -1) {
                dist[na][nb] = dist[a][b] + 1;
                came_from[na][nb] = {a, b};
                came_by[na][nb] = action;
                waiting.push({na, nb});
            }
        }
    }
    if (end_a == -1) {
        cout << "impossible\n";
        return 0;
    }
    vector<string> steps;
    int a = end_a, b = end_b;
    while (a != 0 || b != 0) {
        steps.push_back(action_name[came_by[a][b]] + " -> " + to_string(a) + " " + to_string(b)); // (5)!
        auto [pa, pb] = came_from[a][b];
        a = pa;
        b = pb;
    }
    reverse(steps.begin(), steps.end());
    cout << "steps " << steps.size() << '\n';
    for (const string &s : steps) {
        cout << s << '\n';
    }
    return 0;
}

1. ฟังก์ชันที่คืน pair เขียนค่าที่จะคืนในปีกกาได้เลย {cap_a, b} คือ pair ที่ตัวแรกเป็น cap_a ตัวที่สองเป็น b แบบเดียวกับตอน push pair ลง queue
2. เทได้เท่ากับน้ำที่มีในขวด A หรือที่ว่างที่เหลือในขวด B แล้วแต่อย่างไหนน้อยกว่า
3. สถานะเริ่มต้นคือขวดเปล่าทั้งคู่ (0, 0) ตารางมีขนาด (A + 1) × (B + 1) เพราะน้ำในขวด A มีได้ตั้งแต่ 0 ถึง A
4. เช็กตอนหยิบออก ถ้าถึงเป้าหมายแล้วหยุดได้เลย เพราะ BFS หยิบสถานะออกเรียงตามจำนวนครั้ง สถานะแรกที่ถึงเป้าหมายจึงใช้ครั้งน้อยที่สุด
5. to_string(x) แปลงตัวเลขเป็นสตริง จึงต่อกับสตริงอื่นด้วย + ได้ ใช้ประกอบข้อความของแต่ละขั้นเก็บไว้ก่อน แล้วค่อยพิมพ์ตามลำดับที่กลับแล้ว

9 4 6

steps 8
fill A -> 9 0
pour A into B -> 5 4
empty B -> 5 0
pour A into B -> 1 4
empty B -> 1 0
pour A into B -> 0 1
fill A -> 9 1
pour A into B -> 6 4

ขวด 9 ลิตรกับ 4 ลิตร ตวง 6 ลิตรได้ใน 8 ครั้ง เคล็ดคือเทขวดใหญ่ลงขวดเล็กซ้ำจนเหลือเศษ 1 ลิตรไว้ในขวดเล็ก ขวดเล็กจึงรับได้อีกแค่ 3 ลิตร เติมขวดใหญ่ให้เต็มแล้วเทลงไป ขวดใหญ่จะเหลือ 9 - 3 = 6 ลิตรพอดี มีสถานะแค่ 10 × 5 = 50 แบบ แต่ละแบบลองหกการกระทำ งานรวมเป็น O(AB) ถ้าเป้าหมายไปไม่ถึง queue จะว่างโดยไม่เจอ และพิมพ์ impossible

เทียบกับการลองทุกลำดับ

วิธีจากบทที่ 21 คือลองทุกลำดับการกระทำที่ยาว k ครั้ง เริ่มจาก k = 0 แล้วเพิ่มทีละหนึ่งจนกว่าจะมีลำดับที่ถึงเป้าหมาย ได้จำนวนครั้งน้อยที่สุดเหมือนกัน แต่ต้องลองถึง 6^k ลำดับ วัดบนเครื่องเดียวกับหน้า 19.1 รันแต่ละแบบ 5 รอบ ยกเว้นแถวที่คำตอบเป็น 12 ของการลองทุกลำดับรัน 3 รอบ ตารางเป็นค่ากลาง

คำตอบเพิ่มสองครั้ง การลองทุกลำดับช้าลงหลายเท่าไปจนถึงหลายสิบเท่า เพราะลำดับที่ต้องลองคูณ 36 ลำดับส่วนใหญ่วนอยู่กับสถานะเดิมซ้ำแล้วซ้ำอีก เช่น เติม A แล้วเท A ทิ้ง แล้วเติม A อีก BFS ไม่เสียเวลากับลำดับพวกนี้ เพราะสถานะที่เคยไปแล้วไม่ถูกใส่ queue อีก คำตอบ 34 ครั้งที่การลองทุกลำดับต้องใช้ 6³⁴ ลำดับ BFS ยังเสร็จใน 0.012 วินาที

สถานะที่เป็นข้อความ

บางปริศนาแปลงสถานะเป็นเลขช่องของอาเรย์ได้ยาก ใช้ string เป็นสถานะ แล้วจำระยะด้วย map<string, int> จากบทที่ 20 แทนอาเรย์ ตัวอย่างคือกองแพนเค้กขนาดต่างกันที่เรียงสลับกันอยู่ เขียนเป็นตัวเลขจากแผ่นบนสุดลงไป ทำได้อย่างเดียวคือสอดตะหลิวใต้แผ่นที่ k จากบนแล้วพลิก แผ่นบนสุด k แผ่นจะกลับลำดับ อยากเรียงให้แผ่นเล็กอยู่บน ต้องพลิกอย่างน้อยกี่ครั้ง

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

int main()
{
    string start;
    cin >> start;
    string goal = start;
    sort(goal.begin(), goal.end());
    map<string, int> flips; // (1)!
    map<string, pair<string, int>> came_from;
    queue<string> waiting;
    flips[start] = 0;
    waiting.push(start);
    while (!waiting.empty()) {
        string now = waiting.front();
        waiting.pop();
        if (now == goal) {
            break;
        }
        for (int k = 2; k <= (int)now.size(); k++) {
            string next = now;
            reverse(next.begin(), next.begin() + k); // (2)!
            if (flips.count(next) == 0) { // (3)!
                flips[next] = flips[now] + 1;
                came_from[next] = {now, k};
                waiting.push(next);
            }
        }
    }
    cout << "flips " << flips[goal] << '\n';
    vector<pair<int, string>> steps;
    for (string s = goal; s != start; s = came_from[s].first) {
        steps.push_back({came_from[s].second, s});
    }
    reverse(steps.begin(), steps.end());
    for (auto [k, s] : steps) {
        cout << "flip top " << k << " -> " << s << '\n';
    }
    cout << "states seen " << flips.size() << '\n';
    return 0;
}

1. ระยะของแต่ละสถานะ ถ้ายังไม่มีคีย์นั้นแปลว่ายังไม่เคยไป ไม่ต้องตั้งค่า -1 ให้ทุกสถานะล่วงหน้า
2. พลิก k แผ่นบนคือกลับลำดับ k ตัวแรกของสตริง ใช้ reverse กับช่วง begin() ถึง begin() + k
3. เช็กว่ามีคีย์หรือยังด้วย count ไม่ใช่ flips[next] == 0 เพราะวงเล็บเหลี่ยมสร้างคีย์ใหม่ค่า 0 ให้ทันทีตามหน้า 20.3 และสถานะเริ่มต้นมีระยะ 0 จริงๆ จะถูกนับว่ายังไม่เคยไป แบบเดียวกับแบบที่ 2 ในหน้า 27.3

361524

flips 6
flip top 5 -> 251634
flip top 4 -> 615234
flip top 6 -> 432516
flip top 3 -> 234516
flip top 4 -> 543216
flip top 5 -> 123456
states seen 720

แพนเค้ก 6 แผ่นมีลำดับได้ 6! = 720 แบบ BFS เห็นครบทุกแบบก่อนจะถึงเป้าหมาย ใช้ 6 ครั้ง สถานะแต่ละแบบลองพลิกได้ n - 1 แบบ และทุกครั้งที่สร้างสถานะใหม่ต้องคัดลอกสตริงยาว n กับค้นใน map อีก O(log จำนวนสถานะ) งานรวมจึงเป็น O(n! · n · n log n!) โตเร็วมาก วัดบนเครื่องเดียวกับหน้า 19.1 รัน 5 รอบ ค่ากลางของ 8 แผ่น (40,320 สถานะ) คือ 0.073 วินาทีแบบ -O2 และ 0.157 วินาทีแบบ Code::Blocks ส่วน 9 แผ่น (เห็น 360,997 สถานะ) ใช้ 1.291 วินาทีและ 2.249 วินาที สถานะที่เป็นสตริงกับ map ใช้ง่าย แต่ช้ากว่าอาเรย์หลายเท่า ก่อนเขียนให้นับจำนวนสถานะเสมอ หลักแสนยังพอไหว หลักล้านต้องหาทางแปลงสถานะเป็นตัวเลข

หัวข้อเสริม 0-1 BFS

หัวข้อนี้เป็นหัวข้อเสริม ถ้าอ่านครั้งแรกแล้วยังไม่เข้าใจ ข้ามไปก่อนได้ บทที่ 28 จะมีวิธีที่ใช้ได้กับน้ำหนักทุกแบบ

ถนนบางเส้นในจังหวัดเป็นทางด่วนที่ต้องจ่ายค่าผ่านทาง บางเส้นฟรี คนขับอยากไปจากเมือง 1 ให้ผ่านด่านน้อยที่สุด ไม่สนว่าขับไกลแค่ไหน ถ้าให้ถนนฟรียาว 0 และทางด่วนยาว 1 คำถามคือระยะที่สั้นที่สุดในกราฟที่น้ำหนักมีแค่ 0 กับ 1

BFS ธรรมดาใช้ไม่ได้ เพราะ BFS นับจำนวนถนนที่ผ่าน ไม่ได้รวมค่าผ่านทาง ในภาพ BFS เจอเมือง 2 ก่อนจากถนน 1-2 ตรงๆ ซึ่งต้องจ่ายหนึ่งด่าน และจองเมือง 2 ไว้ตั้งแต่ตอนนั้น ทั้งที่ทาง 1-3-2 ผ่านถนนสองเส้นแต่ไม่เสียด่านเลย ทางที่ผ่านถนนน้อยที่สุดจึงไม่ใช่ทางที่เสียด่านน้อยที่สุดเสมอไป วิธีแก้คือใช้ deque แทน queue ตามหน้า 17.2

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

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

const int MAXN = 200001;
vector<pair<int, int>> adj[MAXN];
int tolls[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, toll;
        cin >> u >> v >> toll;
        adj[u].push_back({v, toll});
        adj[v].push_back({u, toll});
    }
    fill(tolls, tolls + n + 1, INT_MAX);
    deque<int> waiting;
    tolls[1] = 0;
    waiting.push_back(1);
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop_front();
        for (auto [next, toll] : adj[v]) {
            if (tolls[v] + toll < tolls[next]) { // (1)!
                tolls[next] = tolls[v] + toll;
                if (toll == 0) {
                    waiting.push_front(next); // (2)!
                } else {
                    waiting.push_back(next);
                }
            }
        }
    }
    for (int v = 1; v <= n; v++) {
        cout << (tolls[v] == INT_MAX ? -1 : tolls[v]) << (v == n ? '\n' : ' ');
    }
    return 0;
}

1. เริ่มทุกเมืองที่ INT_MAX แปลว่ายังไปไม่ถึง และแก้ทุกครั้งที่ได้ระยะที่น้อยกว่าเดิม ไม่ใช่แค่ครั้งแรก
2. ถนนฟรีใส่หน้า deque ถนนเสียเงินใส่ท้าย

6 7
1 2 1
1 3 0
3 2 0
2 4 1
3 5 1
4 6 0
5 6 1

0 0 0 1 1 1

เมือง 2 ได้ 0 ผ่านเมือง 3 เมือง 6 ได้ 1 ผ่าน 1 3 2 4 6 ซึ่งเสียแค่ด่าน 2-4 ด่านเดียว ทั้งที่ทางนี้ยาวสี่เส้น ถ้าดูระยะที่แต่ละเมืองมีตอนถูกใส่ deque จะเห็นแต่ระยะ d ต่อด้วยระยะ d + 1 แบบเดียวกับ queue ของ BFS เพราะเมืองที่ใส่หน้ามีระยะเท่ากับตัวที่กำลังหยิบ ส่วนเมืองที่ใส่ท้ายมีระยะมากกว่าหนึ่ง เมืองจึงออกจาก deque เรียงตามระยะ มีกรณีเดียวที่ต่างจาก BFS คือเมืองที่ถูกใส่ท้ายไปแล้วด้วยระยะ d + 1 แล้วภายหลังได้ระยะ d จากถนนฟรี จะถูกใส่หน้าอีกครั้ง deque จึงมีเมืองนี้สองที่ ที่อยู่หน้าออกก่อนและแก้เพื่อนบ้านไปครบแล้ว พอที่ค้างอยู่ท้ายถูกหยิบออกมา ระยะของเมืองไม่ได้ลดลงอีก จึงไม่มีเพื่อนบ้านถูกแก้เพิ่ม เสียแค่การไล่รายการเพื่อนบ้านซ้ำ ระยะที่เมืองหนึ่งได้รับมีแค่ d หรือ d + 1 เมื่อ d คือระยะของเมืองที่พบมันเป็นคนแรก จึงถูกแก้ได้ไม่เกินสองครั้ง ใส่และหยิบออกจาก deque ไม่เกินสองครั้ง งานรวมยังเป็น O(V + E)

กราฟที่ซ่อนอยู่ในโจทย์ตารางก็ใช้ 0-1 BFS ได้ เช่น เดินในช่องว่างฟรีแต่ต้องเคลียร์สิ่งที่ขวางทางทีละช่อง ซึ่งจะได้ลองในแบบฝึกหัด หรือเดินตามลูกศรที่พื้นฟรีแต่การเปลี่ยนไปทางอื่นเสียหนึ่งครั้ง

เทียบกับการไล่ทีละจำนวนด่าน

วิธีที่ไม่ต้องใช้ deque คือไล่ทีละ k ตั้งแต่ 0 รอบที่ k เริ่มจากทุกเมืองที่ระยะเป็น k แล้ว BFS ผ่านถนนฟรีอย่างเดียว ทุกเมืองที่ไปถึงได้ระยะ k เหมือนกัน จากนั้นทุกเมืองที่ระยะ k ให้ระยะ k + 1 กับเพื่อนบ้านทางด่วนที่ยังไม่มีระยะ ได้คำตอบถูก แต่ทุกรอบต้องไล่หาเมืองที่ระยะเป็น k จากทุกเมือง จึงเป็น O(K · (V + E)) เมื่อ K คือระยะที่มากที่สุด

วัดบนเครื่องเดียวกับหน้า 19.1 ถนนสายยาวที่เมือง i ต่อกับเมือง i + 1 สลับฟรีกับเสียเงิน และมีทางด่วนเส้นสั้นๆ ที่ข้ามไปสองหรือสามเมืองอีก N/2 เส้นแบบสุ่ม ระยะมากที่สุดจึงโตตาม N รันแต่ละแบบ 5 รอบ ยกเว้นการไล่ทีละจำนวนด่านที่ N ตั้งแต่ 50000 รัน 3 รอบ ตารางเป็นค่ากลาง

N เพิ่มสองเท่า การไล่ทีละจำนวนด่านช้าลงราวสี่เท่า เพราะทั้งจำนวนรอบและงานต่อรอบโตพร้อมกัน ส่วน 0-1 BFS โตตาม N เท่านั้น

ลองทำให้พัง

แบบที่ 1 จองระยะตั้งแต่เจอครั้งแรก

เขียน 0-1 BFS แบบ BFS ปกติ คือให้ระยะครั้งเดียวตอนเจอครั้งแรก แล้วบวกค่าผ่านทางเข้าไป

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

const int MAXN = 200001;
vector<pair<int, int>> adj[MAXN];
int tolls[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, toll;
        cin >> u >> v >> toll;
        adj[u].push_back({v, toll});
        adj[v].push_back({u, toll});
    }
    fill(tolls, tolls + n + 1, -1);
    queue<int> waiting;
    tolls[1] = 0;
    waiting.push(1);
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop();
        for (auto [next, toll] : adj[v]) {
            if (tolls[next] == -1) {
                tolls[next] = tolls[v] + toll;
                waiting.push(next);
            }
        }
    }
    for (int v = 1; v <= n; v++) {
        cout << tolls[v] << (v == n ? '\n' : ' ');
    }
    return 0;
}

6 7
1 2 1
1 3 0
3 2 0
2 4 1
3 5 1
4 6 0
5 6 1

0 1 0 2 1 2

เมือง 2 ได้ 1 ทั้งที่ไปฟรีได้ เพราะตอนหยิบเมือง 1 ออกมา ถนน 1-2 อยู่ก่อนในรายการ เมือง 2 จึงถูกจองด้วยระยะ 1 ตั้งแต่ตอนนั้น พอเมือง 3 พบทางฟรีไปเมือง 2 ทีหลัง ก็แก้ไม่ได้แล้ว ความผิดลามต่อไปถึงเมือง 4 และ 6 ข้อมูลที่ถนนฟรีบังเอิญมาก่อนในรายการจะได้คำตอบถูก ชุดทดสอบส่วนใหญ่จึงผ่าน และตกเฉพาะบางชุด ซึ่งหาสาเหตุยาก เปลี่ยนแค่ queue เป็น deque ก็ยังผิดเหมือนเดิม ตราบใดที่ยังจองตั้งแต่ครั้งแรก

แบบที่ 2 ใส่ท้าย deque ทุกครั้ง

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

if (tolls[v] + toll < tolls[next]) {
    tolls[next] = tolls[v] + toll;
    waiting.push_back(next);
}

กับเมืองในภาพยังได้ 0 0 0 1 1 1 ถูกทุกตัว และกับทุกข้อมูลก็ได้คำตอบถูก เพราะทุกครั้งที่พบทางที่ดีกว่า ระยะถูกแก้และเมืองถูกใส่ queue ใหม่ แต่เมืองไม่ได้ออกจาก queue เรียงตามระยะอีกแล้ว เมืองที่ได้ระยะผิดไปก่อนจะส่งต่อระยะผิดๆ ให้เพื่อนบ้าน แล้วต้องตามแก้ซ้ำทีหลัง ลองกับถนนสายยาวชุดเดียวกับตารางก่อนหน้า นับจำนวนครั้งที่ใส่ deque วัดบนเครื่องเดียวกับหน้า 19.1 รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลาง

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

สรุป

• BFS บนสถานะได้จำนวนครั้งที่น้อยที่สุด สถานะคือจุดยอด การกระทำคือเส้นเชื่อม คำนวณสถานะถัดไปทุกครั้งที่หยิบออก ไม่ต้องสร้างกราฟ
• เวลาของ BFS บนสถานะคือจำนวนสถานะคูณจำนวนการกระทำ นับจำนวนสถานะก่อนเขียนเสมอ
• สถานะที่แปลงเป็นเลขช่องได้ใช้อาเรย์ ไม่ได้ใช้ map และเช็กว่ามีหรือยังด้วย count ไม่ใช่วงเล็บเหลี่ยม
• 0-1 BFS ใช้ deque เส้นยาว 0 ใส่หน้า เส้นยาว 1 ใส่ท้าย และแก้ระยะทุกครั้งที่ได้ค่าน้อยกว่าเดิม ใช้เวลา O(V + E)

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด