#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;
}