-
-
Save cjxgm/b3d594836e4420a80e22 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| #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; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment