Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <stack>
- // moves
- const int d_size = 8;
- const int dx[d_size] = {+1, +1, 0, -1, -1, -1, 0, +1};
- const int dy[d_size] = { 0, +1, +1, +1, 0, -1, -1, -1};
- struct point {
- size_t x, y;
- point() {
- this->x = 0;
- this->y = 0;
- }
- point(const size_t & x, const size_t & y) {
- this->x = x;
- this->y = y;
- }
- point& operator += (const point & other) {
- this->x += other.x;
- this->y += other.y;
- return *this;
- }
- bool operator == (const point & other) const {
- return (this->x == other.x && this->y == other.y);
- }
- };
- size_t n = 0, m = 0;
- bool ans = false;
- std::vector< std::vector<int> > Field;
- point s, t;
- std::queue<point> Q;
- bool good(const point & p) {
- bool b1 = (p.x >= 0 && p.x < n);
- bool b2 = (p.y >= 0 && p.y < m);
- return b1 && b2;
- }
- void bfs(const point & p) {
- for (size_t i = 0; i < d_size; ++i) {
- point new_point = p;
- while (good(new_point += point(dx[i], dy[i])) && Field[new_point.x][new_point.y] != -1)
- if (Field[new_point.x][new_point.y] == 0) {
- Field[new_point.x][new_point.y] = Field[p.x][p.y] + 1;
- Q.push(new_point);
- }
- }
- }
- void rec(std::vector<point> & way) {
- const point p = way[way.size() - 1];
- if (p == t) {
- ans = true;
- std::cout << way.size() - 1 << "\n";
- for (std::vector<point>::const_iterator it = way.begin(); it != way.end(); ++it)
- std::cout << it->x << " " << it->y << "\n";
- return;
- }
- if (Field[p.x][p.y] == -1 || Field[p.x][p.y] + way.size() - 1 != Field[s.x][s.y])
- return;
- for (size_t i = 0; i < d_size; ++i) {
- point new_point = p;
- while (good(new_point += point(dx[i], dy[i])) && Field[new_point.x][new_point.y] != -1) {
- way.push_back(new_point);
- rec(way);
- way.pop_back();
- }
- }
- }
- int main() {
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- std::cin >> n >> m;
- Field.resize(n);
- for (size_t i = 0; i < Field.size(); ++i)
- Field[i].resize(m);
- size_t k = 0;
- std::cin >> k;
- for (size_t i = 0; i < k; ++i) {
- size_t x = 0, y = 0;
- std::cin >> x >> y;
- Field[x][y] = -1;
- }
- std::cin >> s.x >> s.y;
- std::cin >> t.x >> t.y;
- Q.push(t);
- Field[t.x][t.y] = 1;
- while (!Q.empty()) {
- bfs(Q.front());
- Q.pop();
- }
- std::vector<point> way;
- way.push_back(s);
- rec(way);
- if (!ans)
- std::cout << "no_solutions";
- return 0;
- }
Add Comment
Please, Sign In to add comment