Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- const int inf = 100;
- struct kletka
- {
- public:
- int x, y;
- void new_kletka(int x, int y)
- {
- this->x = x;
- this->y = y;
- }
- void print_kletka()
- {
- cout << x+1 << " " << y+1 << " ";
- }
- };
- class vershina
- {
- public:
- int cost;
- kletka* data;
- vershina* prev;
- vershina* next;
- vershina(kletka* data, int cost, vershina* prev = nullptr)
- {
- this->data = data;
- this->cost = cost;
- this->prev = prev;
- this->next = nullptr;
- }
- void print_v()
- {
- cout << data->x + 1 << " " << data->y + 1 << endl;
- }
- };
- class queue
- {
- public:
- queue()
- {
- size = 0;
- head = nullptr;
- tail = nullptr;
- }
- vershina* head;
- vershina* tail;
- int size;
- void push_back(kletka* data, int cost = 0, vershina* prev = nullptr)
- {
- vershina* yzel = new vershina(data, cost, prev);
- if (head == nullptr)
- {
- head = yzel;
- tail = yzel;
- }
- else
- {
- tail->next = yzel;
- tail = yzel;
- }
- size++;
- }
- vershina* pop_front()
- {
- if (size == 0)
- return 0;
- vershina* result = head;
- head = head->next;
- size--;
- return result;
- }
- int GetSize()
- {
- return size;
- }
- };
- class Graph
- {
- public:
- queue red_Q, green_Q;
- int dlina = 0, *dx, *dy;
- bool **board;
- kletka start_red, start_green;
- Graph(int x1, int y1, int x2, int y2)
- {
- start_red.new_kletka(x1, y1);
- start_green.new_kletka(x2, y2);
- board = new bool*[8]{0};
- for (int i = 0; i < 8; i++)
- board[i] = new bool[8]{0};
- board[x1][y1] = 1;
- board[x2][y2] = 1;
- dx = new int[8]{2, 2, 1, 1, -1, -1, -2, -2};
- dy = new int[8]{1, -1, 2, -2, 2, -2, 1, -1};
- if (x1 == x2 && y1 == y2)
- cout << 0;
- else
- poisk(start_red, start_green);
- }
- void poisk(kletka start_red, kletka start_green);
- bool check_access(kletka* a, kletka* b);
- void all_way(vershina* red, vershina* green, int dlina);
- void variant(vershina* a, queue* Q);
- void get_arr();
- };
- void Graph::variant(vershina* a, queue* Q)
- {
- int u = 0, v = 0;
- cout << a->data->x << " " << a->data->y << endl;
- for (int i = 0; i < 8; i++)
- {
- u = a->data->x + dx[i];
- v = a->data->y + dy[i];
- if (u >= 0 && u < 8 && v >= 0 && v < 8 && !board[u][v])
- {
- kletka current;
- current.new_kletka(u, v);
- //current.print_kletka();
- Q->push_back(¤t, a->cost+1, a);
- board[u][v] = 1;
- }
- }
- }
- bool Graph::check_access(kletka* a, kletka* b)
- {
- bool x = false;
- cout << a->x+1 << " " << a->y+1 << endl;
- for (int i = 0; i < 8; i++)
- if (a->x == b->x + dx[i] && a->y == b->y + dy[i] )
- x = true;
- return x;
- }
- void Graph::poisk(kletka start_red, kletka start_green)
- {
- vershina* current = new vershina(&start_red, 0);
- variant(current, &red_Q);
- green_Q.push_back(&start_green);
- while (red_Q.GetSize() != 0 && green_Q.GetSize() != 0)
- {
- vershina** red = new vershina*[red_Q.GetSize()];
- vershina** green = new vershina*[green_Q.GetSize()];
- int red_size = red_Q.GetSize();
- int green_size = green_Q.GetSize();
- for (int i = 0; i < red_size; i++)
- {
- red[i] = red_Q.pop_front();
- // cout << red[i]->data->x + 1 << endl;
- }
- for (int i = 0; i < green_size; i++)
- green[i] = green_Q.pop_front();
- get_arr();
- for (int i = 0; i < red_size; i++)
- for (int j = 0; j < green_size; j++)
- if (check_access(red[i]->data, green[j]->data) == true)
- {
- all_way(red[i], green[j], red[i]->cost);
- return;
- }
- for (int i = 0; i < red_size; i++)
- variant(red[i], &red_Q);
- for (int i = 0; i < green_size; i++)
- variant(green[i], &green_Q);
- }
- cout << -1;
- return;
- }
- void Graph::get_arr()
- {
- for (int i = 0; i < 8; i++)
- {
- for (int j = 0; j < 8; j++)
- {
- cout.width(3);
- cout << board[i][j] << " ";
- }
- cout << endl;
- }
- }
- void Graph::all_way(vershina* red, vershina* green, int dlina)
- {
- kletka* r = new kletka[dlina];
- kletka* g = new kletka[dlina];
- vershina* current_red = red;
- vershina* current_green = green;
- int i = 0;
- while (current_red->data->x != start_red.x or current_red->data->y !=start_red.y)
- {
- r[i] = *current_red->data;
- g[i+1] = *current_green->data;
- current_red = current_red->prev;
- current_green = current_green->prev;
- i++;
- }
- g[0] = r[0];
- cout << red->cost << endl;
- for (int i = dlina-1; i >= 0; i--)
- {
- r[i].print_kletka();
- g[i].print_kletka();
- }
- }
- int main()
- {
- int x, y, x2, y2;
- cin >> x >> y >> x2 >> y2;
- Graph object(x-1, y-1, x2-1, y2-1);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement