Created
July 7, 2014 10:07
-
-
Save anonymous/be4e55d01547810325fe to your computer and use it in GitHub Desktop.
toDebug
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> | |
| using namespace std; | |
| template <int h, int w> | |
| struct Bitmap | |
| { | |
| using size_type = pair<int,int>; | |
| using coord_type = pair<int,int>; | |
| struct Iterator | |
| { | |
| using Value = bool[h][w]; | |
| Iterator(const Value value, int y, int x): value{value}, 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); | |
| } | |
| const bool* operator*() { return &value[y][x]; } | |
| const Iterator& from() { return _from.at(0); } | |
| private: | |
| const Value value; | |
| int y; | |
| int x; | |
| vector<const Iterator> _from; | |
| }; | |
| using const_iterator_type = Iterator; | |
| constexpr size_type size() { return size_type{h, w}; } | |
| const_iterator_type cbegin() const | |
| { | |
| return Iterator{value, 0, 0}; | |
| } | |
| const_iterator_type crbegin() const | |
| { | |
| return Iterator{value, h-1, w-1}; | |
| } | |
| void read() | |
| { | |
| for (int y=0; y<h; y++) | |
| for (int x=0; x<w; x++) | |
| cin >> value[y][x]; | |
| } | |
| private: | |
| bool value[h][w]; | |
| }; | |
| template < | |
| class Maze, | |
| class Iter = typename Maze::const_iterator_type, | |
| class Coord = typename Maze::coord_type | |
| > | |
| Iter operator+(const Iter& it, const Coord& co) | |
| { | |
| return Iter{it, co}; | |
| } | |
| template <class Maze, class Path = vector<typename Maze::coord_type>> | |
| Path solve_maze(const Maze& maze) | |
| { | |
| template < | |
| class Base = | |
| queue<typename Maze::const_iterator_type> | |
| > | |
| struct Queue: public Base | |
| { | |
| struct visited {}; | |
| void push(const value_type& x) | |
| { | |
| if (*x) throw visited{}; | |
| Base::push(x); | |
| x.wallize(); | |
| } | |
| operator bool() { return !empty(); } | |
| }; | |
| 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 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{}; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment