38(actually3984).cc

//
#include <stdexcept>
#include <vector>
#include <queue>
#include <utility>
#include <iostream>
#include <memory>
using namespace std;

struct Bitmap
{
	using size_type = pair<int,int>;
	using coord_type = pair<int,int>;

	struct Iterator
	{
		using Value = bool*;

		Iterator(Value value, int h, int w, int y, int x)
			: value{value}, h{h}, w{w}, y{y}, x{x}
		{
		}

		Iterator(const Iterator& it, const coord_type& co)
			: Iterator{it}
		{
			auto y = co.first;
			auto x = co.second;
			this->y += y;
			this->x += x;
			if (this->y < 0 || this->y >= h || this->x < 0 || this->x >= w)
				throw out_of_range{""};
			_from.clear();
			_from.emplace(_from.cend(), it);
		}

		bool operator*() const { return value[y*w+x]; }
		const Iterator& from() const { return _from.at(0); }
		coord_type pos() const { return coord_type{y, x}; }
		void wallize() { value[y*w+x] = true; }
		bool operator==(const Iterator& rhs)
		{
			return value == rhs.value && y == rhs.y && x == rhs.x;
		}

	private:
		Value value;
		int h;
		int w;
		int y;
		int x;
		vector<Iterator> _from;
	};
	using const_iterator_type = Iterator;

	size_type size() const { return size_type{h, w}; }
	const_iterator_type cbegin() const
	{
		return Iterator{&*value, h, w, 0, 0};
	}

	const_iterator_type crbegin() const
	{
		return Iterator{&*value, h, w, h-1, w-1};
	}

	void read()
	{
		cin >> h >> w;
		value = shared_ptr<bool>(new bool[w*h]);
		for (int y=0; y<h; y++)
			for (int x=0; x<w; x++)
				cin >> (&*value)[y*w+x];
	}

private:
	int h;
	int w;
	shared_ptr<bool> value;
};

template <class Iter, class Coord>
Iter operator+(const Iter& it, const Coord& co)
{
	return Iter{it, co};
}

template <
	class Maze,
	class Base = queue<typename Maze::const_iterator_type>
>
struct Queue: public Base
{
	struct visited {};

	void push(typename Base::value_type x)
	{
		if (*x) throw visited{};
		Base::push(x);
		x.wallize();
	}

	operator bool() { return !Base::empty(); }
};

template <class Maze, class Path = vector<typename Maze::coord_type>>
Path solve_maze(const Maze& maze)
{
	constexpr typename Maze::coord_type dirs[] = {
		typename Maze::coord_type{-1,  0},
		typename Maze::coord_type{+1,  0},
		typename Maze::coord_type{ 0, -1},
		typename Maze::coord_type{ 0, +1},
	};

	auto end = maze.crbegin();
	Queue<Maze> Q;
	Q.push(maze.cbegin());
	while (Q) {
		auto it = Q.front();
		Q.pop();

		for (int i=0; i<sizeof(dirs)/sizeof(dirs[0]); i++)
			try {
				auto next = it + dirs[i];
				if (next == end) {
					Path path;
					try {
						for (; true; next = next.from())
							path.push_back(next.pos());
					} catch (...) {}
					return Path{path.rbegin(), path.rend()};
				}
				Q.push(next);
			}
			catch (...) {}
	}

	struct no_solution {};
	throw no_solution{};
}


int main()
{
	Bitmap maze;
	maze.read();
	for (const auto& co: solve_maze(maze))
		cout << "(" << co.first << ", " << co.second << ")" << endl;
}