27.4 DFS และ BFS บนตาราง

โจทย์เขาวงกต แผนที่เกาะ ไฟลาม และหุ่นยนต์เดินในห้อง เป็นโจทย์กราฟที่ออกบ่อย แต่ไม่มีใครให้รายการเส้นเชื่อมมา โจทย์ให้แค่ตารางตัวอักษรแบบบทที่ 7 หน้านี้มองตารางเป็นกราฟ แล้วใช้ BFS กับ DFS จากหน้า 27.2 และ 27.3 ได้เลยโดยไม่ต้องสร้าง adjacency list หาทางที่สั้นที่สุดในเขาวงกต นับเกาะ แล้ววัดว่าทำไมการจำลองทีละนาทีแบบบทที่ 7 ไม่ทันกับตารางใหญ่

ตารางคือกราฟ

ให้ทุกช่องที่เดินได้เป็นจุดยอด และช่องที่ติดกันในสี่ทิศเป็นเส้นเชื่อม ตาราง R × C จึงเป็นกราฟที่มีจุดยอดไม่เกิน RC จุด และเส้นเชื่อมไม่เกิน 2RC เส้น เพื่อนบ้านของช่อง (r, c) ไม่ต้องเก็บไว้ที่ไหน คำนวณได้ทุกครั้งด้วยอาเรย์ทิศทาง dr กับ dc ในหน้า 7.4 ส่วนที่เปลี่ยนจากหน้า 27.3 มีสามอย่าง

• dist เป็นตารางสองมิติ vector<vector<int>> ตามหน้า 16.2 แทนอาเรย์มิติเดียว
• queue เก็บ pair<int, int> คือแถวกับคอลัมน์ ตอนหยิบออกแตกเป็นสองตัวแปรด้วย auto [r, c]
• เพื่อนบ้านต้องผ่านการเช็กขอบตาราง และต้องไม่ใช่กำแพง ก่อนจะดู dist

เขาวงกต

หาจำนวนก้าวที่น้อยที่สุดจาก S ไป E ก้าวได้ทีละช่องในสี่ทิศ ห้ามเข้าช่อง # แล้ววาดเส้นทางลงบนแผนที่ด้วย * เส้นทางใช้แนวคิดเดียวกับ parent ในหน้า 27.3 แต่จดว่ามาถึงช่องนี้ด้วยทิศไหนแทน เพราะเก็บเลขทิศตัวเดียวง่ายกว่าเก็บพิกัดของพ่อสองตัว

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

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int main()
{
    int rows, cols;
    cin >> rows >> cols;
    vector<string> grid(rows);
    for (int r = 0; r < rows; r++) {
        cin >> grid[r];
    }
    vector<vector<int>> dist(rows, vector<int>(cols, -1));
    vector<vector<int>> came_by(rows, vector<int>(cols, -1)); // (1)!
    queue<pair<int, int>> waiting;
    int goal_r = -1, goal_c = -1;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 'S') {
                dist[r][c] = 0;
                waiting.push({r, c});
            } else if (grid[r][c] == 'E') {
                goal_r = r;
                goal_c = c;
            }
        }
    }
    while (!waiting.empty()) {
        auto [r, c] = waiting.front();
        waiting.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                came_by[nr][nc] = d; // (2)!
                waiting.push({nr, nc});
            }
        }
    }
    if (dist[goal_r][goal_c] == -1) {
        cout << "no way out\n";
        return 0;
    }
    cout << "steps " << dist[goal_r][goal_c] << '\n';
    int r = goal_r, c = goal_c;
    while (grid[r][c] != 'S') {
        int d = came_by[r][c];
        r -= dr[d]; // (3)!
        c -= dc[d];
        if (grid[r][c] == '.') {
            grid[r][c] = '*';
        }
    }
    for (int i = 0; i < rows; i++) {
        cout << grid[i] << '\n';
    }
    return 0;
}

1. came_by[r][c] คือเลขทิศ 0 ถึง 3 ที่ใช้ก้าวเข้ามาที่ช่องนี้
2. จดพร้อมกับให้ระยะ เหมือน parent ช่องหนึ่งได้ระยะครั้งเดียว จึงจดทิศครั้งเดียว
3. เดินถอยหลังหนึ่งก้าว คือลบทิศที่ใช้เดินเข้ามาออก แล้ววนจนถึง S ระหว่างทางเปลี่ยนช่อง . เป็น *

7 11
###########
#S..#.....#
#.#.#.###.#
#.#...#...#
#.#####.#.#
#.......#E#
###########

steps 16
###########
#S..#.....#
#*#.#.###.#
#*#...#***#
#*#####*#*#
#*******#E#
###########

ภาพนี้คือระยะของทุกช่องที่ BFS คำนวณได้ ช่องที่ระบายพื้นคือเส้นทางที่โปรแกรมวาด

ทางเดินด้านบนผ่าน (1, 5) ก็ไปถึง E ใน 16 ก้าวเท่ากัน สองทางมาบรรจบกันที่ช่องเหนือ E สองช่อง ซึ่งได้ระยะ 14 จากทางไหนก็ได้ โปรแกรมเลือกทางที่ช่องเพื่อนบ้านถูกหยิบออกจาก queue ก่อน ลองกับเขาวงกต 5 × 7 ในหน้า 7.3 ด้วย

5 7
#######
#S..#.#
#.#.#.#
#...E.#
#######

steps 5
#######
#S..#.#
#*#.#.#
#***E.#
#######

ทุกช่องเข้า queue ไม่เกินครั้งเดียว และแต่ละครั้งดูเพื่อนบ้านสี่ช่อง เวลาจึงเป็น O(RC) ตาราง 1000 × 1000 มีหนึ่งล้านช่อง ทำได้สบายในหนึ่งวินาที โปรแกรมแบบเดียวกันที่ตัดส่วนวาดเส้นทางออก รันกับแผนที่ 1001 × 1001 ใช้หน่วยความจำสูงสุด 10.3 MB วัดจาก PeakWorkingSet ทั้งหมดอยู่นอก stack เพราะ vector ขอหน่วยความจำระหว่างรัน

นับเกาะ

แผนที่ทะเลมี # เป็นแผ่นดิน . เป็นน้ำ แผ่นดินที่ติดกันในสี่ทิศอยู่เกาะเดียวกัน ให้นับเกาะและหาขนาดของเกาะที่ใหญ่ที่สุด นี่คือการนับส่วนเชื่อมต่อในหน้า 27.2 บนตาราง ไล่ทุกช่อง เจอแผ่นดินที่ยังไม่เคยไปเมื่อไร นับเกาะเพิ่มหนึ่งแล้วเดินให้ทั่วเกาะ การเดินแบบนี้มีชื่อเรียกว่า flood fill เหมือนเทน้ำลงช่องหนึ่งแล้วน้ำไหลไปทั่วทุกช่องที่ติดกัน เขียนด้วย recursion ได้สั้นมาก

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

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
int rows, cols;
vector<string> grid;
vector<vector<bool>> seen; // (1)!

int fill_island(int r, int c)
{
    seen[r][c] = true;
    int cells = 1;
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '#' && !seen[nr][nc]) {
            cells += fill_island(nr, nc); // (2)!
        }
    }
    return cells;
}

int main()
{
    cin >> rows >> cols;
    grid.resize(rows);
    for (int r = 0; r < rows; r++) {
        cin >> grid[r];
    }
    seen.assign(rows, vector<bool>(cols, false)); // (3)!
    int islands = 0, largest = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '#' && !seen[r][c]) {
                islands++;
                int cells = fill_island(r, c);
                cout << "island " << islands << " starts at " << r << ' ' << c << " size " << cells << '\n';
                largest = max(largest, cells);
            }
        }
    }
    cout << "islands " << islands << " largest " << largest << '\n';
    return 0;
}

1. ตาราง bool สองมิติแบบ vector ซ้อน vector ในหน้า 16.2 ประกาศไว้นอก main แบบว่างก่อน เพราะ fill_island ต้องใช้ด้วย แล้วค่อยกำหนดขนาดเมื่อรู้ rows กับ cols
2. ขนาดของเกาะคือช่องนี้หนึ่งช่อง บวกขนาดของส่วนที่ไปถึงได้จากเพื่อนบ้านแต่ละทิศที่ยังไม่เคยไป
3. assign(rows, vector<bool>(cols, false)) ทิ้งของเดิมแล้วให้ seen มี rows แถว แต่ละแถวเป็น vector<bool> ยาว cols ช่องที่เป็น false ทุกช่อง

5 9
##....#..
#...###..
..#....##
.###..#..
.....##..

island 1 starts at 0 0 size 3
island 2 starts at 0 6 size 4
island 3 starts at 2 2 size 4
island 4 starts at 2 7 size 2
island 5 starts at 3 6 size 3
islands 5 largest 4

ช่อง (2, 7) กับ (3, 6) แตะกันแค่มุม จึงเป็นคนละเกาะ ถ้าโจทย์นับทแยงว่าติดกันด้วย เปลี่ยน dr กับ dc เป็น 8 ทิศแบบหน้า 7.4 และวนถึง 8 ส่วนอื่นไม่ต้องแก้

recursion ลึกเท่าขนาดเกาะ

ฟังก์ชัน fill_island ลงลึกไปตามช่องที่ติดกันเรื่อยๆ เกาะที่เป็นแผ่นดินทั้งแผ่นจึงเรียกซ้อนกันเท่าจำนวนช่องของเกาะ บนเครื่องที่เขียนเอกสารนี้ ป้อนแผนที่ N × N ที่เป็นแผ่นดินทั้งหมด รันจาก PowerShell ค่าละ 10 ครั้ง

แผนที่แค่ 150 × 150 ก็พังด้วย 0xC00000FD แล้ว ทั้งที่โจทย์ตารางให้ขนาดถึง 1000 × 1000 เป็นปกติ ฟังก์ชันนี้มีตัวแปร local หลายตัว แต่ละชั้นจึงกินที่มาก ลึกได้น้อยกว่าเกณฑ์ราว 25,000 ชั้นในหน้า 27.2 และแบบ -O2 ก็พังที่ขนาดเดียวกับแบบ Code::Blocks ตรงกับที่หน้า 27.2 บอกว่าตัวเลขของ -O2 ขึ้นกับรูปของฟังก์ชัน วางใจไม่ได้ ให้ใช้ BFS แทน โครงเหมือน BFS ของเขาวงกต ส่วนที่เปลี่ยนคือ เริ่ม BFS ใหม่จากทุกช่องแผ่นดินที่ยังไม่เคยไปแบบนับส่วนเชื่อมต่อในหน้า 27.2 ใช้ seen แทน dist เพราะไม่ต้องรู้ระยะ เดินเข้าเฉพาะช่อง # แทนการเลี่ยงช่อง # ไม่ต้องจดทิศหรือวาดเส้นทาง และนับช่องตอนหยิบออก

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

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int main()
{
    int rows, cols;
    cin >> rows >> cols;
    vector<string> grid(rows);
    for (int r = 0; r < rows; r++) {
        cin >> grid[r];
    }
    vector<vector<bool>> seen(rows, vector<bool>(cols, false));
    int islands = 0, largest = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != '#' || seen[r][c]) {
                continue;
            }
            islands++;
            int cells = 0;
            queue<pair<int, int>> waiting;
            seen[r][c] = true;
            waiting.push({r, c});
            while (!waiting.empty()) {
                auto [cr, cc] = waiting.front(); // (1)!
                waiting.pop();
                cells++;
                for (int d = 0; d < 4; d++) {
                    int nr = cr + dr[d];
                    int nc = cc + dc[d];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '#' && !seen[nr][nc]) {
                        seen[nr][nc] = true;
                        waiting.push({nr, nc});
                    }
                }
            }
            cout << "island " << islands << " starts at " << r << ' ' << c << " size " << cells << '\n';
            largest = max(largest, cells);
        }
    }
    cout << "islands " << islands << " largest " << largest << '\n';
    return 0;
}

1. ชื่อ r กับ c ถูกใช้เป็นตัวแปรของลูปข้างนอกแล้ว ช่องที่หยิบออกมาจึงใช้ชื่อ cr กับ cc ถ้าใช้ชื่อซ้ำ ตัวข้างในจะบังตัวข้างนอกไว้ อ่านแล้วสับสนง่าย

5 9
##....#..
#...###..
..#....##
.###..#..
.....##..

island 1 starts at 0 0 size 3
island 2 starts at 0 6 size 4
island 3 starts at 2 2 size 4
island 4 starts at 2 7 size 2
island 5 starts at 3 6 size 3
islands 5 largest 4

ได้ผลเท่าเดิมทุกบรรทัด และกับแผ่นดินทั้งแผ่น 1000 × 1000 ก็ไม่พัง เพราะ queue อยู่นอก stack ใช้ stack ของเราเองแบบหน้า 27.2 แทน queue ก็ได้ผลเท่ากัน เพราะนับเกาะไม่สนใจลำดับ

เร็วขึ้นแค่ไหน

ก่อนรู้จัก BFS วิธีที่น้องน่าจะคิดออกคือจำลองทีละนาทีแบบเกมชีวิตในหน้า 7.4 นาทีแรกมีแค่ S ทุกนาทีถัดไป ทุกช่องว่างที่ติดกับช่องที่ไปถึงแล้วกลายเป็นช่องที่ไปถึง ทำจนกว่า E จะถูกไปถึง จำนวนนาทีคือคำตอบ หัวใจของวิธีนี้คือลูปนี้ ซึ่งสแกนทั้งตารางทุกนาที

vector<string> next_minute = reached;
bool changed = false;
for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
        if (reached[r][c] == '#' || reached[r][c] == 'S') {
            continue;
        }
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && reached[nr][nc] == 'S') {
                next_minute[r][c] = 'S';
                changed = true;
                break;
            }
        }
    }
}

คำตอบถูกเสมอ เพราะนาทีที่ k คือชั้นที่ k ของ BFS พอดี แต่หนึ่งนาทีใช้ O(RC) และต้องทำเท่ากับจำนวนก้าวของคำตอบ ทั้งหมดเป็น O(RC × คำตอบ) แผนที่ที่หนักที่สุดคือทางงูเลื้อย ซึ่งทางเดินเลี้ยวไปมาจนยาวราวครึ่งหนึ่งของจำนวนช่อง วัดบนเครื่องเดียวกับหน้า 19.1 แผนที่ทางงูเลื้อยขนาด N × N รันแต่ละแบบ 5 รอบ ยกเว้นการจำลองที่ N = 151 และ 201 รัน 3 รอบ ตารางเป็นค่ากลาง

N เพิ่มสองเท่า การจำลองช้าลงสิบกว่าเท่า เพราะทั้งจำนวนช่องและจำนวนนาทีโตเป็นสี่เท่าพร้อมกัน ที่ N = 1001 งานมากกว่าที่ N = 201 ราวหกร้อยเท่า คาดว่าแบบ -O2 ต้องใช้ราว 14 นาที จึงไม่ได้รัน ส่วน BFS ที่ N = 1001 ใช้ไม่ถึงหนึ่งในสิบวินาที การจำลองทีละรอบยังเหมาะกับโจทย์ที่ถามว่า "ผ่านไป K นาทีแล้วเป็นยังไง" เมื่อ K น้อย แบบไฟป่าในแบบฝึกหัดบทที่ 7 แต่ถ้าถามว่า "กี่นาทีจึงถึง" ให้ใช้ BFS

ลองทำให้พัง

แบบที่ 1 จดตอนหยิบออกจาก queue

หน้า 27.3 สอนว่าให้ระยะตอนใส่ queue ลองฝืนดู ใช้ตาราง taken จดว่าช่องไหนถูกหยิบออกแล้ว จดตอนหยิบออก และใส่เพื่อนบ้านลง queue ถ้าเพื่อนบ้านยังไม่ถูกหยิบ ส่วนนี้ของโปรแกรมเป็นแบบนี้

while (!waiting.empty()) {
    auto [r, c] = waiting.front();
    waiting.pop();
    taken[r][c] = true;
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] != '#' && !taken[nr][nc]) {
            dist[nr][nc] = dist[r][c] + 1;
            waiting.push({nr, nc});
            pushes++;
        }
    }
}

ระยะที่ได้ยังถูก เพราะทุกช่องยังออกจาก queue เรียงตามชั้น แต่ช่องเดียวกันถูกใส่ซ้ำจากเพื่อนบ้านทุกตัวที่ออกจาก queue ก่อนมัน แต่ละสำเนาที่ถูกหยิบออกก็ใส่เพื่อนบ้านซ้ำอีก จำนวนสำเนาจึงทบไปเรื่อยๆ ลองกับตารางโล่ง N × N ไม่มีกำแพง S อยู่มุมซ้ายบน E อยู่มุมขวาล่าง นับจำนวนครั้งที่ใส่ queue วัดบนเครื่องเดียวกับหน้า 19.1 รัน 3 รอบ ยกเว้น N = 16 รันรอบเดียว

ตารางแค่ 16 × 16 ช่อง ใส่ queue หกร้อยล้านครั้ง เพิ่มขึ้นราวสิบห้าเท่าทุกครั้งที่ N เพิ่มสอง ทั้งที่แบบจดตอนใส่ใช้แค่ 256 ครั้ง โปรแกรมแบบนี้ผ่านเขาวงกตแคบๆ ในตัวอย่างได้ เพราะทางเดินกว้างหนึ่งช่องแทบไม่มีทางให้ซ้ำ แล้วไปตกเวลาเกินกับชุดทดสอบที่เป็นที่โล่ง จดตอนใส่ queue เสมอ

แบบที่ 2 เช็กว่าเป็นทางเดินด้วย '.'

ในโปรแกรม maze-path เขียนเงื่อนไขเดินว่า grid[nr][nc] == '.' แทน grid[nr][nc] != '#' เพราะคิดว่าทางเดินคือจุด แล้วรันกับเขาวงกตเดิม

7 11
###########
#S..#.....#
#.#.#.###.#
#.#...#...#
#.#####.#.#
#.......#E#
###########

no way out

ช่อง E ไม่ใช่ . จึงไม่เคยถูกเดินเข้าไป ระยะของ E ค้างเป็น -1 โจทย์ตารางมักมีตัวอักษรพิเศษปนในแผนที่ เช่น S E ประตู หรือกุญแจ ให้เช็กสิ่งที่ ห้ามเดิน แทนการเช็กสิ่งที่เดินได้ และทดสอบกับตัวอย่างที่ E อยู่ติดกับ S ด้วย

สรุป

• ตารางคือกราฟที่ทุกช่องเป็นจุดยอด เพื่อนบ้านคำนวณจาก dr กับ dc ไม่ต้องสร้าง adjacency list ใช้เวลา O(RC)
• BFS บนตารางใช้ dist สองมิติกับ queue ของ pair<int, int> จดทิศที่เดินเข้ามาเพื่อวาดเส้นทางย้อนกลับ
• นับเกาะคือนับส่วนเชื่อมต่อ flood fill แบบ recursion พังตั้งแต่แผนที่ราว 150 × 150 ใช้ BFS หรือ stack ของเราเอง
• การจำลองทีละนาทีให้คำตอบเท่ากับ BFS แต่ใช้ O(RC × คำตอบ) ทางงูเลื้อยทำให้ไม่ทัน
• จดตอนใส่ queue ไม่ใช่ตอนหยิบออก และเช็กสิ่งที่ห้ามเดินแทนสิ่งที่เดินได้