labyrinth.cpp

#include <iostream>
#include <optional>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>

// key : x, y
// value : nullopt:wall, 0:not yet discovered not 0:distance
using Point = std::pair<int, int>;
using Map = std::map<Point, std::optional<int>>;

constexpr int xsize = 8;
constexpr int ysize = 8;

std::vector<Point> create_wall() {
    return {
        {1, 0},
        {6, 0},
        {1, 1},
        {3, 1},
        {3, 2},
        {5, 2},
        {6, 2},
        {0, 3},
        {2, 3},
        {3, 3},
        {7, 3},
        {3, 4},
        {4, 4},
        {5, 4},
        {7, 4},
        {1, 5},
        {7, 5},
        {3, 6},
        {5, 6}
    };
}

Map create_map() {
    auto walls = create_wall();
    Map map;
    for (int y = 0; y < ysize; ++y) {
        for (int x = 0; x < xsize; ++x) {
            Point p{x, y};
            if (std::find(walls.begin(), walls.end(), p) != walls.end()) {
                map[p] = std::nullopt;
            } else {
                map[p] = 0;
            }
        }
    }
    return map;
}

void print_map(const Map& map) {
    for (int y = 0; y < ysize; ++y) {
        for (int x = 0; x < xsize; ++x) {
            auto p = map.at({x, y});
            if (p == std::nullopt) {
                std::cout << "xx";
            } else if (p == 999) {
                std::cout << "SS";
            } else {
                std::cout << std::setw(2) << std::setfill('0') << p.value();
            }
        }
        std::cout << std::endl;
    }
}

int main() {
    Point goal{7, 0};
    Point start{0, 7};
    Map map = create_map();
    std::vector<Point> nexts = {start};
    int distance = 1;
    map[start] = 999;
    while (map[goal] == 0) {
        std::vector<Point> temp_nexts;
        for (const auto& [x, y] : nexts) {
            Point p1{x + 1, y};
            if (auto it = map.find(p1); it != map.end() && it->second == 0) {
                it->second = distance;
                temp_nexts.push_back(it->first);
            }
            Point p2{x - 1, y};
            if (auto it = map.find(p2); it != map.end() && it->second == 0) {
                it->second = distance;
                temp_nexts.push_back(it->first);
            }
            Point p3{x, y + 1};
            if (auto it = map.find(p3); it != map.end() && it->second == 0) {
                it->second = distance;
                temp_nexts.push_back(it->first);
            }
            Point p4{x, y - 1};
            if (auto it = map.find(p4); it != map.end() && it->second == 0) {
                it->second = distance;
                temp_nexts.push_back(it->first);
            }
        }
        nexts = temp_nexts;
        ++distance;
    }
    print_map(map);
}