Mô tả bài toán

Bài toán yêu cầu tìm đường đi ngắn nhất trong một mê cung 5x5.

Giải pháp

Với kích thước nhỏ như vậy, có nhiều cách để giải quyết vấn đề này. Một phương pháp đơn giản là sử dụng BFS để tìm đường đi ngắn nhất và đồng thời ghi lại đường đi.

Trong quá trình BFS, ta không chỉ lưu trữ vị trí hiện tại mà còn lưu chuỗi ký tự thể hiện đường đi. Điều này giúp ta biết được đường đi ngắn nhất khi gặp điểm đích lần đầu tiên.

Mã nguồn

Đây là đoạn mã C++ sử dụng BFS:

#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

const int MAX_SIZE = 6;
const int INF = 0x3f3f3f3f;
int maze[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];

struct Position {
    int row, col;
    string path;
};

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

void findPath() {
    queue<Position> q;
    q.push({0, 0, "(0, 0)"});
    visited[0][0] = true;

    while (!q.empty()) {
        Position current = q.front();
        q.pop();

        if (current.row == 4 && current.col == 4) {
            cout << current.path << endl;
            return;
        }

        for (int i = 0; i < 4; ++i) {
            int newRow = current.row + dr[i];
            int newCol = current.col + dc[i];
            string newPath = current.path + " (" + to_string(newRow) + ", " + to_string(newCol) + ")";

            if (newRow >= 0 && newRow < 5 && newCol >= 0 && newCol < 5 && !visited[newRow][newCol] && !maze[newRow][newCol]) {
                visited[newRow][newCol] = true;
                q.push({newRow, newCol, newPath});
            }
        }
    }
}

int main() {
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            cin >> maze[i][j];
        }
    }

    fill(&visited[0][0], &visited[0][0] + MAX_SIZE * MAX_SIZE, false);
    findPath();

    return 0;
}

Đây là đoạn mã C++ sử dụng kết hợp BFS và DFS:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAX_SIZE = 6;
const int INF = 0x3f3f3f3f;
int maze[MAX_SIZE][MAX_SIZE];
int dist[MAX_SIZE][MAX_SIZE];

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

void bfs() {
    queue<pair<int, int>> q;
    q.push({0, 0});
    dist[0][0] = 0;

    while (!q.empty()) {
        pair<int, int> current = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int newRow = current.first + dr[i];
            int newCol = current.second + dc[i];

            if (newRow >= 0 && newRow < 5 && newCol >= 0 && newCol < 5 && dist[newRow][newCol] == INF && !maze[newRow][newCol]) {
                dist[newRow][newCol] = dist[current.first][current.second] + 1;
                q.push({newRow, newCol});
            }
        }
    }
}

void dfs(int row, int col, int steps, vector<pair<int, int>>& path) {
    if (row == 4 && col == 4) {
        if (steps == dist[4][4]) {
            for (auto& p : path) {
                cout << "(" << p.first << ", " << p.second << ")" << endl;
            }
        }
        return;
    }

    for (int i = 0; i < 4; ++i) {
        int newRow = row + dr[i];
        int newCol = col + dc[i];

        if (newRow >= 0 && newRow < 5 && newCol >= 0 && newCol < 5 && dist[newRow][newCol] == steps + 1 && !maze[newRow][newCol]) {
            path.push_back({newRow, newCol});
            dfs(newRow, newCol, steps + 1, path);
            path.pop_back();
        }
    }
}

int main() {
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            cin >> maze[i][j];
        }
    }

    fill(&dist[0][0], &dist[0][0] + MAX_SIZE * MAX_SIZE, INF);
    bfs();

    vector<pair<int, int>> path = {{0, 0}};
    dfs(0, 0, 0, path);

    return 0;
}