Tìm kiếm theo chiều rộng trên ma trận (BFS) trong C++

BFS trên ma trận 2D: tìm khoảng cách ngắn nhất từ source (giá trị 2) đến destination (giá trị 3).

• 0: không đi được
• 1: có thể di chuyển
• 2: source
• 3: destination

Thuật toán BFS

• Tìm tọa độ source (2) và destination (3)
• Khởi tạo mảng dist[][] = INT_MAX, dist[source] = 0
• Queue lưu pair(row, col)
• Duyệt 4 hướng: trái, phải, lên, xuống
• Nếu ô mới hợp lệ (1 hoặc 3) và dist mới < dist cũ → cập nhật, push queue
• Trả về dist[destination]

Code C++

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

int findDistance(int row, int col, int mat[][5]) {
    int si, sj, di, dj;
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++) {
            if (mat[i][j] == 2) { si = i; sj = j; }
            if (mat[i][j] == 3) { di = i; dj = j; }
        }
    int dist[row][col];
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++) dist[i][j] = INT_MAX;

    queue> q;
    q.push({si, sj});
    dist[si][sj] = 0;

    while (!q.empty()) {
        int x = q.front().first, y = q.front().second; q.pop();
        // Left
        if (y-1 >= 0 && (mat[x][y-1] == 1 || mat[x][y-1] == 3))
            if (dist[x][y] + 1 < dist[x][y-1]) {
                dist[x][y-1] = dist[x][y] + 1;
                q.push({x, y-1});
            }
        // Right
        if (y+1 < col && (mat[x][y+1] == 1 || mat[x][y+1] == 3))
            if (dist[x][y] + 1 < dist[x][y+1]) {
                dist[x][y+1] = dist[x][y] + 1;
                q.push({x, y+1});
            }
        // Up
        if (x-1 >= 0 && (mat[x-1][y] == 1 || mat[x-1][y] == 3))
            if (dist[x][y] + 1 < dist[x-1][y]) {
                dist[x-1][y] = dist[x][y] + 1;
                q.push({x-1, y});
            }
        // Down
        if (x+1 < row && (mat[x+1][y] == 1 || mat[x+1][y] == 3))
            if (dist[x][y] + 1 < dist[x+1][y]) {
                dist[x+1][y] = dist[x][y] + 1;
                q.push({x+1, y});
            }
    }
    return dist[di][dj];
}

int main() {
    int row = 5, col = 5;
    int mat[5][5] = {
        {1,0,0,2,1},
        {1,0,1,1,1},
        {0,1,1,2,0},
        {3,1,0,0,1},
        {1,1,0,0,1}
    };
    int ans = findDistance(row, col, mat);
    if (ans == INT_MAX) cout << "No Path Found";
    else cout << "Shortest Distance: " << ans;
    return 0;
}

Kết quả

The Shortest Distance between Source and Destination is: 4