SHARE
TWEET

Untitled

a guest May 26th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. #include <fstream>
  4. #include <vector>
  5. #include <stack>
  6.  
  7. struct coord{
  8.     unsigned int x, y;
  9. };
  10.  
  11. void check (std::vector<std::vector<coord>> &last, std::queue<coord> &qu, std::vector<std::vector<char>> &maze, int x, int y, coord &coordinate) {
  12.     last[x][y] = coordinate;
  13.     coord temp;
  14.     temp.x = x;
  15.     temp.y = y;
  16.     qu.push(temp);
  17.     maze[x][y] = '+';
  18. }
  19.  
  20. int main() {
  21.     unsigned int n, x, y;
  22.     coord start, finish, coordinate;
  23.     std::vector<std::vector<char>> maze;
  24.     std::vector<std::vector<coord>> last;
  25.  
  26.     std::ifstream inp("input.txt");
  27.     inp >> n >> start.y >> start.x >> finish.x >> finish.y;
  28.  
  29.     maze.resize(n);
  30.     last.resize(n);
  31.     for (int i = 0; i < n; ++i) {
  32.         maze[i].resize(n);
  33.         last[i].resize(n);
  34.     }
  35.  
  36.     for (int i = 0; i < n; ++i) {
  37.         for (int j = 0; j < n; ++j) {
  38.             inp >> maze[i][j];
  39.         }
  40.     }
  41.     inp.close();
  42.  
  43.     start.x--;
  44.     start.y--;
  45.     finish.x--;
  46.     finish.y--;
  47.     std::stack<coord> path;
  48.     std::queue<coord> qu;
  49.  
  50.     maze[start.x][start.y] = '+';
  51.     coordinate.x = start.x;
  52.     coordinate.y = start.y;
  53.     qu.push(coordinate);
  54.  
  55.     while (!qu.empty()) {
  56.         coordinate = qu.front();
  57.         x = coordinate.x;
  58.         y = coordinate.y;
  59.         qu.pop();
  60.  
  61.         if (coordinate.x == finish.y && coordinate.y == finish.x) {
  62.             break;
  63.         }
  64.  
  65.         if (x > 0 && maze[x - 1][y] == '.') {
  66.             check(last, qu, maze, x-1, y, coordinate);
  67.         }
  68.  
  69.         if (x < n - 1 && maze[x + 1][y] == '.') {
  70.             check(last, qu, maze, x+1, y, coordinate);
  71.         }
  72.  
  73.         if (y > 0 && maze[x][y - 1] == '.') {
  74.             check(last, qu, maze, x, y-1, coordinate);
  75.         }
  76.  
  77.         if (y < n - 1 && maze[x][y + 1] == '.') {
  78.             check(last, qu, maze, x, y+1, coordinate);
  79.         }
  80.     }
  81.  
  82.     while (coordinate.x != start.x || coordinate.y != start.y) {
  83.         path.push(coordinate);
  84.         coordinate = last[coordinate.x][coordinate.y];
  85.     }
  86.     int res = 0;
  87.     res = path.size();
  88.    
  89.     std::ofstream outp("output.txt");
  90.  
  91.     outp << res;
  92.     outp.close();
  93.     return 0;
  94. }
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