API tools faq
paste
Gistrec

Поиск пути в лабиринте (Обход в ширину)

Gistrec
Feb 24th, 2018
1,106
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.02 KB | None | 0 0
raw download clone embed print report
  1. #pragma once
  2. #include <iostream>
  3.  
  4. #include <vector>
  5. #include <queue>
  6.  
  7. #define WALL false
  8. #define WAY true
  9.  
  10. using namespace std;
  11.  
  12. // Нужно, чтобы добавлять координату пути
  13. // В очередь или вектор
  14. struct Vector2 {
  15.     int x;
  16.     int y;
  17.     Vector2(int x, int y) : x(x), y(y) {};
  18. };
  19.  
  20. //
  21. // Класс лабиринта
  22. // TODO: добавить описание
  23. //
  24. class Labyrinth {
  25. public:
  26.     // X - кол-во строк
  27.     // Y - кол-во столбцов
  28.     Labyrinth(int max_x, int max_y) : x(max_x), y(max_y) {
  29.         // Инициализируем матрицу лабиринта
  30.         labyrinth.resize(max_x);
  31.         for (int i = 0; i < max_x; ++i) {
  32.             labyrinth[i].resize(max_y);
  33.             for (int j = 0; j < max_y; ++j) {
  34.                 labyrinth[i][j] = WAY;
  35.             }
  36.         }
  37.     }
  38.  
  39.     void setWall(int x, int y) {
  40.         labyrinth[x][y] = WALL;
  41.     }
  42.  
  43.     void deleteWall(int x, int y) {
  44.         labyrinth[x][y] = WAY;
  45.     }
  46.  
  47.     // Поиск выхода в лабиринте из точки start_x, start_y
  48.     // Используется волновой алгоритм
  49.     //
  50.     // x, y - начальная позиция
  51.     void findExit(int start_x, int start_y) {
  52.         // Инициализируем матрицу размера x*y, заполненную -1
  53.         // где хранится расстояние от старта до текущей клетки
  54.         vector<vector<int>> distantion(x, vector<int>(y, -1));
  55.         distantion[start_x][start_y] = 0;
  56.  
  57.         // Очередь, в которой будут вершины, которые нужно обойти
  58.         queue<Vector2> queue;
  59.         queue.push(Vector2(start_x, start_y));
  60.  
  61.         while (!queue.empty()) {
  62.             // Вынесем функцию для обработки вершины
  63.             // в встраиваемую функцию, чтобы не мозолило глаза
  64.             if (nextStep(queue, distantion)) {
  65.                 Vector2 finish = queue.front();
  66.                 printWay(distantion, finish.x, finish.y);
  67.                 cout << endl;
  68.                 return;
  69.             }
  70.         }
  71.     }
  72.  
  73.     // Функция возвращает true, если вершина найдена
  74.     // Vector2 вершины находится в начале очереди
  75.     inline bool nextStep(queue<Vector2> &queue, vector<vector<int>> &distantion) {
  76.         // Обрабатываемемая вершина
  77.         Vector2 position = queue.front();
  78.         // Если мы нашли выход из лабиринта
  79.         if (position.x == 0 || position.x == x ||
  80.             position.y == 0 || position.y == y) {
  81.             return true;
  82.         }
  83.         queue.pop();
  84.         // Дистанция от старта для текущей вершины
  85.         int current_distantion = distantion[position.x][position.y];
  86.  
  87.         // Проверяем четыре вершины (выше, ниже, правее, левее)
  88.         // На то, нужно ли их просматривать (проходить)
  89.         checkPositioin(queue, distantion, current_distantion, position.x, position.y + 1);
  90.         checkPositioin(queue, distantion, current_distantion, position.x, position.y - 1);
  91.         checkPositioin(queue, distantion, current_distantion, position.x + 1, position.y);
  92.         checkPositioin(queue, distantion, current_distantion, position.x - 1, position.y);
  93.  
  94.         return false;
  95.     }
  96.  
  97.     // Смотрим, если вершина - путь, и расстояние от нее до старта больше, чем
  98.     // расстояние от старта, до соседней вершины - то 'еще раз проходим эту вершину'
  99.     // так как найден более короткий путь для нее
  100.     inline void checkPositioin(queue<Vector2> &queue, vector<vector<int>> &distantion, int current_distantion, int x, int y) {
  101.         if (labyrinth[x][y] == WAY && (distantion[x][y] == -1 || distantion[x][y] > current_distantion)) {
  102.             queue.push(Vector2(x, y));
  103.             distantion[x][y] = current_distantion + 1;
  104.         }
  105.     }
  106.  
  107.     // Выбрать среди соседних ячейку,
  108.     // помеченную числом на 1 меньше числа в текущей ячейке
  109.     // и перейти в выбранную ячейку
  110.     inline void printWay(vector<vector<int>> &distantion, int x, int y) {
  111.         int need_distance = distantion[x][y] - 1;
  112.         if (need_distance == -1) return; // Конец цикла, если текущая клетка - старт
  113.         // Для четырех вершин (выше, ниже, правее, левее) смотрим
  114.         if (y != this->y && distantion[x][y + 1] == need_distance) {
  115.             printWay(distantion, x, y + 1);
  116.             cout << "L";
  117.         } else if (y != 0 && distantion[x][y - 1] == need_distance) {
  118.             printWay(distantion, x, y - 1);
  119.             cout << "R";
  120.         } else if (x != this->x && distantion[x + 1][y] == need_distance) {
  121.             printWay(distantion, x + 1, y);
  122.             cout << "U";
  123.         } else if (x != 0 && distantion[x - 1][y] == need_distance) {
  124.             printWay(distantion, x - 1, y);
  125.             cout << "D";
  126.         }
  127.     }
  128.  
  129. private:
  130.     int x; // кол-во строк
  131.     int y; // кол-во столбцов
  132.  
  133.     vector<vector<bool>> labyrinth; // Лабиринт
  134. };
Advertisement
Comments
  • Izleo
    Izleo
    97 days
    # CSS 0.85 KB | 0 0
    view report reply
    1. ✅ Leaked Exploit Documentation:
    2.  
    3. https://docs.google.com/document/d/1dOCZEHS5JtM51RITOJzbS4o3hZ-__wTTRXQkV1MexNQ/edit?usp=sharing
    4.  
    5. This made me $13,000 in 2 days.
    6.  
    7. Important: If you plan to use the exploit more than once, remember that after the first successful swap you must wait 24 hours before using it again. Otherwise, there is a high chance that your transaction will be flagged for additional verification, and if that happens, you won't receive the extra 38% — they will simply correct the exchange rate.
    8. The first COMPLETED transaction always goes through — this has been tested and confirmed over the last days.
    9.  
    10. Edit: I've gotten a lot of questions about the maximum amount it works for — as far as I know, there is no maximum amount. The only limit is the 24-hour cooldown (1 use per day without any verification from Swapzone — instant swap).
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!