Advertisement
Guest User

Untitled

a guest
Nov 19th, 2019
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <queue>
  5.  
  6. struct Point {
  7.     int x, y;
  8.  
  9.     void add(const Point& p) {
  10.         x += p.x;
  11.         y += p.y;
  12.     }
  13.    
  14.     bool operator ==(const Point& p) const {
  15.         return (x == p.x && y == p.y);
  16.     }
  17. };
  18.  
  19. bool passable(const Point& p, const std::vector<std::string>& v) {
  20.     const char PASSABLE = '.';
  21.     const std::size_t SIZE = v.size();
  22.     //Bound Check
  23.     if (p.x < 0 || p.y < 0 || p.x >= SIZE || p.y >= SIZE)
  24.         return false;
  25.     return v[p.x][p.y] == PASSABLE;
  26. }
  27.  
  28. int getMinimumMoves(std::vector<std::string> grid, int startX, int startY, int endX, int endY)
  29. {
  30.     const Point START{ startX, startY };
  31.     const Point END  {   endX,    endY};
  32.     const std::size_t N = grid.size();
  33.    
  34.     const Point DIRECTIONS[4] = {
  35.         { 0,-1 }, //NORTH
  36.         { 1, 0 }, //EAST
  37.         { 0, 1 }, //SOUTH
  38.         {-1, 0 }, //WEST
  39.     };
  40.  
  41.     const Point SENTINEL{ -1,-1 };
  42.  
  43.     if (START == END)
  44.         return 0;
  45.  
  46.     std::vector<bool> visited(N * N, false);
  47.     int distance = 0;
  48.  
  49.     std::queue<Point> q;
  50.  
  51.     q.push(START);
  52.     q.push(SENTINEL);
  53.     visited[START.y + START.x * N] = true;
  54.  
  55.     while (!q.empty()) {
  56.         const Point point = q.front();
  57.         q.pop();
  58.  
  59.         if (point == SENTINEL && !q.empty()) {
  60.             q.push(SENTINEL);
  61.             distance++;
  62.         }
  63.  
  64.         for (int i = 0; i < 4; i++) {
  65.             for (Point p = point; passable(p, grid); p.add(DIRECTIONS[i])) {
  66.                 if (p == END)
  67.                     return ++distance;
  68.                 else if (!visited[p.x + p.y * N]) {
  69.                     visited[p.x + p.y * N] = true;
  70.                     q.push(p);
  71.                 }
  72.             }
  73.         }
  74.     }
  75.  
  76.     return -1;
  77. }
  78.  
  79. int main(int argc, char** argv)
  80. {
  81.     ////вход
  82.     unsigned N;
  83.     std::vector<std::string> grid;
  84.     Point start, end;
  85.  
  86.     std::cin >> N;
  87.  
  88.     std::string buffReader;
  89.     grid.reserve(N);
  90.     buffReader.reserve(N);
  91.  
  92.     for (int i = 0; i < N; i++) {
  93.         std::cin >> buffReader;
  94.         grid.push_back(buffReader);
  95.     }
  96.  
  97.     std::cin >> start.x >> start.y
  98.              >> end.x   >> end.y;
  99.  
  100.     //изход
  101.     std::cout << getMinimumMoves(grid, start.x, start.y, end.x, end.y);
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement