Board Find Path BFS

[Eliguli]

Algorithm that finds the max amount of coins for any arbitrary board of coins treasure_map.hpp

#ifndef TREASURE_MAP_HPP
#define TREASURE_MAP_HPP

#include <iostream>
#include <iomanip>
#include <random>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>

using namespace std;

enum Directions {
    none,
    right,
    down,
    left,
    up,
    both
};

class TreasureMap {
public:
    TreasureMap(int size);
    TreasureMap(const TreasureMap& tm) : size(tm.size) {}
    ~TreasureMap();

    static void ensure_order(pair<int, int>& start, pair<int, int>& end);
    void initGold(pair<int, int> start, pair<int, int> end);
    void printBoard();
    int findMaxGold(pair<int, int> start, pair<int, int> end);
    Directions** directionMatrix(pair<int, int> start, pair<int, int> end);
    void printDirections(Directions** dirs, pair<int, int> start, pair<int, int> end);
    vector<vector<Directions>> findPaths(Directions** dirs, pair<int, int> start, pair<int, int> end);
    void printPaths(const vector<vector<Directions>>& paths, pair<int, int> start, pair<int, int> end);

private:
    int size;
    int** gold;
    int** maxGold;

    void initArray(int** &arr);
    void freeMemory(int** arr);
    void generateDistribution(int** arr, mt19937& gen, uniform_int_distribution<>& dis);
};

#endif // TREASURE_MAP_HPP

treasure_map.cpp

#include "treasure_map.hpp"

TreasureMap::TreasureMap(int size) : size(size) {
    initArray(gold);
    initArray(maxGold);
}

TreasureMap::~TreasureMap() {
    freeMemory(gold);
    freeMemory(maxGold);
}

void TreasureMap::ensure_order(pair<int, int>& start, pair<int, int>& end) {
    if (start.first > end.first) {
        swap(start.first, end.first);
    }
    if (start.second > end.second) {
        swap(start.second, end.second);
    }
}

void TreasureMap::initArray(int** &arr) {
    arr = new int*[size];
    for (int i = 0; i < size; i++) {
        arr[i] = new int[size];
    }
}

void TreasureMap::freeMemory(int** arr) {
    for (int i = 0; i < size; i++) {
        delete[] arr[i];
    }
    delete[] arr;
}

void TreasureMap::generateDistribution(int** arr, mt19937& gen, uniform_int_distribution<>& dis) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            arr[i][j] = dis(gen);
        }
    }
}

void TreasureMap::initGold(pair<int, int> start, pair<int, int> end) {
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(1, 9);

    generateDistribution(gold, gen, dis);
    gold[start.first][start.second] = 0;
    gold[end.first][end.second] = 0;
}

void TreasureMap::printBoard() {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            cout << setw(3) << gold[i][j] << " ";
        }
        cout << endl;
    }

    cout << endl << "Max gold matrix: " << endl;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            cout << setw(3) << maxGold[i][j] << " ";
        }
        cout << endl;
    }
}

int TreasureMap::findMaxGold(pair<int, int> start, pair<int, int> end) {
    maxGold[start.first][start.second] = gold[start.first][start.second];
    int dx = (start.first > end.first) ? -1 : 1;
    int dy = (start.second > end.second) ? -1 : 1;

    for (int i = start.first + dx; i != end.first + dx; i += dx) {
        maxGold[i][start.second] = maxGold[i - dx][start.second] + gold[i][start.second];
    }
    for (int j = start.second + dy; j != end.second + dy; j += dy) {
        maxGold[start.first][j] = maxGold[start.first][j - dy] + gold[start.first][j];
    }

    for (int i = start.first + dx; i != end.first + dx; i += dx) {
        for (int j = start.second + dy; j != end.second + dy; j += dy) {
            maxGold[i][j] = gold[i][j] + max(maxGold[i - dx][j], maxGold[i][j - dy]);
        }
    }
    return maxGold[end.first][end.second];
}

Directions** TreasureMap::directionMatrix(pair<int, int> start, pair<int, int> end) {
    Directions** dirs = new Directions*[size];
    for (int i = 0; i < size; i++) {
        dirs[i] = new Directions[size];
        for (int j = 0; j < size; j++) {
            dirs[i][j] = Directions::none;
        }
    }

    int dx = (start.first > end.first) ? -1 : 1;
    int dy = (start.second > end.second) ? -1 : 1;

    for (int i = start.first + dx; i != end.first + dx; i += dx) {
        dirs[i][start.second] = (start.first > end.first) ? Directions::up : Directions::down;
    }

    for (int j = start.second + dy; j != end.second + dy; j += dy) {
        dirs[start.first][j] = (start.second > end.second) ? Directions::left : Directions::right;
    }

    for (int i = start.first + dx; i != end.first + dx; i += dx) {
        for (int j = start.second + dy; j != end.second + dy; j += dy) {
            if (maxGold[i - dx][j] > maxGold[i][j - dy]) {
                dirs[i][j] = (dx == 1) ? Directions::down : Directions::up;
            } else if (maxGold[i - dx][j] < maxGold[i][j - dy]) {
                dirs[i][j] = (dy == 1) ? Directions::right : Directions::left;
            } else {
                dirs[i][j] = Directions::both;
            }
        }
    }
    return dirs;
}

void TreasureMap::printDirections(Directions** dirs, pair<int, int> start, pair<int, int> end) {
    bool reverse_rows = start.first > end.first;
    bool reverse_cols = start.second > end.second;

    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            cout << setw(3);
            Directions dir = dirs[i][j];

            switch (dir) {
                case Directions::none:
                    cout << "N";
                    break;
                case Directions::down:
                    cout << "U";
                    break;
                case Directions::right:
                    cout << "L";
                    break;
                case Directions::left:
                    cout << "R";
                    break;
                case Directions::up:
                    cout << "D";
                    break;
                case Directions::both:
                    cout << "B";
                    break;           
            }
        }
        cout << endl;
    }
}

vector<vector<Directions>> TreasureMap::findPaths(Directions** dirs, pair<int, int> start, pair<int, int> end) {
    vector<vector<Directions>> all_paths;
    stack<pair<int, int>> positions;
    stack<vector<Directions>> paths;

    positions.push(end);
    paths.push({});

    while (!positions.empty()) {
        auto [r, c] = positions.top();
        auto current_path = paths.top();
        positions.pop();
        paths.pop();

        if (r == start.first && c == start.second) {
            reverse(current_path.begin(), current_path.end());
            all_paths.push_back(current_path);
            continue;
        }

        if (dirs[r][c] == Directions::right || dirs[r][c] == Directions::both) {
            if (c > start.second) {
                auto new_path = current_path;
                new_path.push_back(Directions::right);
                positions.push({r, c - 1});
                paths.push(new_path);
            }
        }

        if (dirs[r][c] == Directions::down || dirs[r][c] == Directions::both) {
            if (r > start.first) {
                auto new_path = current_path;
                new_path.push_back(Directions::down);
                positions.push({r - 1, c});
                paths.push(new_path);
            }
        }

        if (dirs[r][c] == Directions::left || dirs[r][c] == Directions::both) {
            if (c < start.second) {
                auto new_path = current_path;
                new_path.push_back(Directions::left);
                positions.push({r, c + 1});
                paths.push(new_path);
            }
        }

        if (dirs[r][c] == Directions::up || dirs[r][c] == Directions::both) {
            if (r < start.first) {
                auto new_path = current_path;
                new_path.push_back(Directions::up);
                positions.push({r + 1, c});
                paths.push(new_path);
            }
        }
    }

    return all_paths;
}

void TreasureMap::printPaths(const vector<vector<Directions>>& paths, pair<int, int> start, pair<int, int> end) {
    bool reverse_rows = start.first > end.first;
    bool reverse_cols = start.second > end .second;

    for (const auto& path : paths) {
        for (auto dir : path) {
            cout << setw(3);
            switch (dir) {
                case Directions::down:
                    cout << ("D"); // Up if reversed, down otherwise
                    break;
                case Directions::right:
                    cout << ("R"); // Left if reversed, right otherwise
                    break;
                case Directions::left:
                    cout << ("L"); // Right if reversed, left otherwise
                    break;
                case Directions::up:
                    cout << ("U"); // Down if reversed, up otherwise
                    break;
                default:
                    break;
            }
        }
        cout << endl;
    }
}

main.cpp

#include "treasure_map.hpp"

int main() {
    int size = 10;
    TreasureMap board(size);

    int start_x, start_y, end_x, end_y;
    cout << "Enter the coordinates of the start position (x, y) and end position (x, y), "
         << "the range should be between 0 and " << (size - 1) << endl;
    cin >> start_x >> start_y >> end_x >> end_y;
    pair<int, int> start = {start_x, start_y};
    pair<int, int> end = {end_x, end_y};

    board.initGold(start, end);

    // ensure_order(start, end);
    int maxGold = board.findMaxGold(start, end);

    cout << endl;
    board.printBoard();
    cout << "Max gold: " << maxGold << endl;

    Directions** dirs = board.directionMatrix(start, end);
    board.printDirections(dirs, start, end);

    vector<vector<Directions>> paths = board.findPaths(dirs, start, end);
    cout << "All possible paths: " << endl;
    board.printPaths(paths, start, end);

    return 0;
}