SHARE
TWEET

Untitled

bbescos Feb 21st, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /******************************************************************************
  2.  
  3.                               Online C++ Compiler.
  4.                Code, Compile, Run and Debug C++ program online.
  5. Write your code in this editor and press "Run" button to compile and execute it.
  6.  
  7. *******************************************************************************/
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. #include <queue>
  12.  
  13. using namespace std;
  14.  
  15. struct Point {
  16.     int x;
  17.     int y;
  18.     Point(int x, int y) : x(x), y(y) {}
  19. };
  20.  
  21. bool InMap(const vector<vector<int>>& map, const Point& p) {
  22.     return (p.x >= 0 && p.x < map.size() && p.y >= 0 && p.y < map[0].size());
  23. }
  24.  
  25. void print_map(const vector<vector<int>>& map) {
  26.     for (int i = 0; i < map.size(); ++i) {
  27.         for (int j = 0; j < map[0].size(); ++j) {
  28.             std::cout << map[i][j] << " ";
  29.         }
  30.         std::cout << std::endl;
  31.     }
  32. }
  33.  
  34. bool PathExists(const vector<vector<int>>& map, const Point& ini_pos, const Point& fin_pos, int& len_path, const int neighboring  = 4) {
  35.    
  36.     vector<vector<int>> dist_map(map.size(), vector<int> (map[0].size(), -1));
  37.     dist_map[ini_pos.x][ini_pos.y] = 0;
  38.    
  39.      vector<vector<int>> neighbors_map;
  40.     if (neighboring == 4) {
  41.         neighbors_map = {{-1, 0},
  42.                         {1, 0},
  43.                         {0, -1},
  44.                         {0, 1}};
  45.     }
  46.     else {
  47.         neighbors_map = {{-1, 0},
  48.                         {-1, 1},
  49.                         {-1, -1},
  50.                         {1, -1},
  51.                         {1, 0},
  52.                         {1, 1},
  53.                         {0, -1},
  54.                         {0, 1}};
  55.     }
  56.    
  57.     queue<Point> qPoints;
  58.     qPoints.push(ini_pos);
  59.     int dist = 1;
  60.    
  61.     while (!qPoints.empty()) {
  62.        
  63.         int nPoints = qPoints.size ();
  64.        
  65.         while (nPoints > 0) {
  66.             Point current = qPoints.front();
  67.             qPoints.pop();
  68.        
  69.             for (int i = 0; i < 4; ++i) {
  70.                 Point p = Point(current.x + neighbors_map[i][0], current.y + neighbors_map[i][1]);
  71.                 if (InMap(map, p) && map[p.x][p.y] == 0 && dist_map[p.x][p.y] == -1) {
  72.                     qPoints.push(p);
  73.                     dist_map[p.x][p.y] = dist;
  74.                 }
  75.             }
  76.             nPoints--;
  77.         }
  78.         ++dist;
  79.     }
  80.  
  81.     print_map(dist_map);
  82.  
  83.     len_path = dist_map[fin_pos.x][fin_pos.y];
  84.    
  85.     return (dist_map[fin_pos.x][fin_pos.y] != -1);
  86. }
  87.  
  88.  
  89. int main()
  90. {
  91.     vector<vector<int>> map = {{0, 0, 0, 0, 1, 0},
  92.                             {0, 0, 0, 0, 1, 0},
  93.                             {0, 0, 0, 1, 1, 0},
  94.                             {0, 0, 0, 0, 1, 0},
  95.                             {0, 1, 1, 0, 1, 0}};
  96.  
  97.     Point ini_pos(0, 0);
  98.     Point fin_pos(2, 5);
  99.  
  100.     print_map(map);
  101.  
  102.     std::cout << std::endl;
  103.    
  104.     int len_path = 0;
  105.  
  106.     bool path_exists = PathExists(map, ini_pos, fin_pos, len_path);
  107.    
  108.     std::cout << path_exists << std::endl;
  109.    
  110.     std::cout << "Path length: " << len_path << std::endl;
  111.  
  112.     return 0;
  113. }
RAW Paste Data
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
 
Top