Pasted

#include <iostream>
#include <algorithm>
#include <array>
#include <queue>
#include <stack>
#include <iomanip>
 
#define х -1
#define о  0
 
enum class SearchType {
    BFS, // Обход в ширину
    DFS  // Обход в глубину
};
 
template <size_t row, size_t col>
using Matrix = std::array<std::array<int, col>, row>;
 
struct Point {
    int x;
    int y;
 
    Point(int x, int y) : x(x), y(y) {};
 
    bool operator==(const Point & other) const { 
        return x == other.x && y == other.y;
    }
 
    std::vector<Point> getNearestPoints() const {
        return { Point(x + 1, y), Point(x - 1, y), Point(x, y + 1), Point(x, y - 1) };
    }
};
 
Point get(std::queue<Point>& container) { return container.front(); }
Point get(std::stack<Point>& container) { return container.top();   }
 
template <SearchType type, typename Labyrinth>
bool search(Labyrinth & labyrinth, Point start, Point end) {
    using ContainerType = std::conditional_t<type == SearchType::BFS, std::queue<Point>, std::stack<Point>>;
    
    ContainerType queue;
    
    labyrinth[start.x][start.y] = 1;
    queue.push(start);
 
    while (!queue.empty()) {
        const Point point = get(queue);
        queue.pop();
 
        const int value = labyrinth[point.x][point.y];
        
        if (point == end) return true;
 
        // Обходим соседние вершины
        for (const auto near : point.getNearestPoints()) {
            if (labyrinth[near.x][near.y] == 0) {
                labyrinth[near.x][near.y] = value + 1;
                std::cout << "Add " << near.x << " " << near.y << std::endl;
                queue.push(near);
            }
        }
    }
    return false;
}
 
template <typename Matrix>
std::vector<Point> getPath(const Matrix& labyrinth, Point end) {
    std::vector<Point> path;
    path.reserve(labyrinth[end.x][end.y]);
 
    Point current = end;
 
    while (labyrinth[current.x][current.y] != 1) {
        const int find = labyrinth[current.x][current.y] - 1;
 
        for (const auto near : current.getNearestPoints()) {
            if (labyrinth[near.x][near.y] == find) {
                path.push_back(near);
                current = near;
                break;
            }
        }
    }
 
    path.push_back(end);
 
    std::reverse(path.begin(), path.end());
 
    return path;
}
 
int main() {
    constexpr size_t row = 7U;
    constexpr size_t col = 6U;
 
    Matrix<row, col> labyrinth = {{
        { х, х, х, х, х, х},
        { х, о, о, о, о, х},
        { х, о, о, о, о, х},
        { х, о, о, о, о, х},
        { х, о, о, о, о, х},
        { х, о, о, о, о, х},
        { х, х, х, х, х, х}
    }};
 
    Point start(3, 3);
    Point end(1, 1);
 
    auto result = search<SearchType::DFS>(labyrinth, start, end);
 
    for (auto row : labyrinth) {
        for (auto cols : row) {
            std::cout << std::setw(3) << cols;
        }
        std::cout << std::endl;
    }
 
    if (result) {
        auto path = getPath(labyrinth, end);
        for (const auto point : path) {
            std::cout << point.x << " " << point.y << std::endl;
        }
    }
 
    return 0;
}