Breadth First Search บน Matrix (Grid) ใน C++

โจทย์

กำหนด 2D Grid/ Matrix หา Shortest Path จาก Source (2) ไป Destination (3) โดยเดินได้เฉพาะ Cell = 1 (หรือ 3) ไม่เดินได้ Cell = 0 ใช้ BFS หาระยะทางสั้นที่สุด

Cell Values

• 0: Blocked/Wall
• 1: Free Path
• 2: Source
• 3: Destination

แนวคิด: BFS บน Grid

• Queue เก็บ (row, col)
• Distance Array เก็บระยะทางจาก Source
• 4 Directions: Up, Down, Left, Right
• เจอ Destination → Return Distance

โค้ด C++

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

int shortestPathBFS(vector<vector<int>>& grid) {
    int rows = grid.size();
    if (rows == 0) return -1;
    int cols = grid[0].size();
    
    // Find Source and Destination
    int sr = -1, sc = -1, dr = -1, dc = -1;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 2) { sr = i; sc = j; }
            if (grid[i][j] == 3) { dr = i; dc = j; }
        }
    }
    if (sr == -1 || dr == -1) return -1;
    
    // Directions: Up, Down, Left, Right
    vector<pair<int,int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    
    vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
    queue<pair<int,int>> q;
    
    q.push({sr, sc});
    dist[sr][sc] = 0;
    
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        
        if (r == dr && c == dc) {
            return dist[r][c]; // Found destination
        }
        
        for (auto [dR, dC] : dirs) {
            int nr = r + dR, nc = c + dC;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                grid[nr][nc] != 0 && // Not blocked
                dist[nr][nc] == INT_MAX) { // Not visited
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    
    return -1; // No path
}

int main() {
    vector<vector<int>> grid = {
        {1, 0, 0, 2, 1},
        {1, 0, 1, 1, 1},
        {0, 1, 1, 2, 0}, // Note: Two 2's? Use first found
        {3, 1, 0, 0, 1},
        {1, 1, 0, 0, 1}
    };
    
    int ans = shortestPathBFS(grid);
    if (ans == -1) {
        cout << "No Path Found" << endl;
    } else {
        cout << "Shortest Distance: " << ans << endl;
    }
    
    // Test 2: Simple case
    vector<vector<int>> grid2 = {
        {2, 1, 1},
        {0, 0, 1},
        {1, 1, 3}
    };
    cout << "Test 2: " << shortestPathBFS(grid2) << endl; // 4
    
    // Test 3: No path
    vector<vector<int>> grid3 = {
        {2, 0, 3},
        {0, 0, 0}
    };
    cout << "Test 3: " << shortestPathBFS(grid3) << endl; // -1
    
    return 0;
}

Complexity

• Time: O(R × C) - Visit each cell at most once
• Space: O(R × C) - Distance Array + Queue

Optimizations

• ใช้ vector<int> 1D แทน 2D: dist[r * cols + c]
• Early Exit: Return ทันทีเจอ Destination
• Bidirectional BFS: เริ่มจาก Source และ Destination พร้อมกัน (เร็วขึ้น ~2x)

Variations

• 8 Directions: เพิ่ม Diagonal (8-connected)
• Weighted Grid: ใช้ Dijkstra / 0-1 BFS
• Multiple Sources: Multi-source BFS (Push all sources initially)
• Find All Distances: ไม่ Early Exit, คืน Distance Array ทั้งหมด

ผลลัพธ์

Shortest Distance: 4
Test 2: 4
Test 3: No Path Found

สรุป

BFS on Grid = Shortest Path ใน Unweighted Grid ใช้ Queue + Distance Array + 4 Directions Template สำคัญสำหรับ Maze, Game Pathfinding, Robot Navigation - LeetCode 1091, 1293, etc.