c++实现黄金矿工算法完整代码

黄金矿工（Gold Miner）算法通常是指用于解决最短路径问题的算法之一，比如在迷宫中寻找最短路径。这个算法在计算机科学中主要用于教学和理解图的搜索策略，如广度优先搜索（BFS）或深度优先搜索（DFS）。在C++中，我们可以使用邻接矩阵或邻接表来表示迷宫的图，然后进行搜索。

以下是一个简单的C++实现，使用了邻接矩阵和深度优先搜索（DFS）：

#include <iostream>
#include <vector>
#include <queue>

// 定义迷宫矩阵
const int EMPTY = 0, WALL = 1, GOLD = 2;

class GoldMiner {
public:
    // 初始化迷宫矩阵
    void init(int rows, int cols, std::vector<std::vector<int>>& maze) {
        for (int i = 0; i < rows; ++i)
            for (int j = 0; j < cols; ++j)
                maze[i][j] = (i == 0 || j == 0 || i == rows - 1 || j == cols - 1) ? WALL : EMPTY;
    }

    // 搜索最短路径并打印结果
    void search(int startRow, int startCol, std::vector<std::vector<int>>& maze) {
        visited[startRow][startCol] = true;
        std::queue<pair<int, int>> q;
        q.push({startRow, startCol});

        while (!q.empty()) {
            auto [currentRow, currentCol] = q.front();
            q.pop();

            if (maze[currentRow][currentCol] == GOLD) {
                printPath(currentRow, currentCol);
                return;
            }

            for (auto &[directionRow, directionCol] : directions) {
                int newRow = currentRow + directionRow;
                int newCol = currentCol + directionCol;

                if (isValidMove(newRow, newCol, maze)) {
                    maze[newRow][newCol] = GOLD; // 标记为已访问过
                    visited[newRow][newCol] = true;
                    q.push({newRow, newCol});
                }
            }
        }
    }

private:
    bool isValidMove(int row, int col, std::vector<std::vector<int>>& maze) {
        return row >= 0 && row < maze.size() && col >= 0 && col < maze.size() && !visited[row][col];
    }

    void printPath(int endRow, int endCol) {
        std::cout << "Path from starting position to gold: ";
        for (int i = endRow; i >= 0; --i) {
            for (int j = endCol; j >= 0; --j) {
                if (maze[i][j] == GOLD) {
                    std::cout << "G";
                } else {
                    break;
                }
            }
            std::cout << "\n";
        }
    }

    std::vector<std::vector<bool>> visited(maze.size(), std::vector<bool>(maze.size(), false));
    std::vector<std::pair<int, int>> directions = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; // 上下左右四个方向
};

int main() {
    int rows = 5, cols = 5;
    std::vector<std::vector<int>> maze(rows, std::vector<int>(cols));
    // 创建你的迷宫
    // ...

    GoldMiner miner;
    miner.init(rows, cols, maze);
    miner.search(0, 0, maze); // 从左上角开始搜索

    return 0;
}