Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2020
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. bool grid[1001][1001];
  8. int path[1000][1000][2];
  9.  
  10.  
  11. int main() {
  12.     ios_base::sync_with_stdio(false);
  13.     cin.tie(nullptr);
  14.  
  15.     int w = 0, h = 0, x1 = 0, y1 = 0, x2 = 0, y2 = 0;
  16.     cin >> w >> h >> x1 >> y1 >> x2 >> y2;
  17.     for (int i = 1; i <= h; i++) {
  18.         for (int j = 1; j <= w; j++) {
  19.             grid[i][j] = getchar() == 46;
  20.         }
  21.         getchar();
  22.     }
  23.  
  24.     queue<vector<int>> queue;
  25.     queue.push({y2, x2});
  26.  
  27.     while (!queue.empty()) {
  28.         auto cur = queue.front();
  29.         queue.pop();
  30.  
  31.         int y = cur[0];
  32.         int x = cur[1];
  33.         grid[y][x] = false;
  34.  
  35.         if (x == x1 && y == y1) {
  36.             cout << "YES\n";
  37.             while (x != x2 || y != y2) {
  38.                 cout << x << " " << y << "  ";
  39.                 int old_x = x, old_y = y;
  40.                 y = path[old_y][old_x][0];
  41.                 x = path[old_y][old_x][1];
  42.             }
  43.             cout << x << " " << y << "  ";
  44.             return 0;
  45.         }
  46.  
  47.         if (grid[y - 1][x]) {
  48.             queue.push({ y - 1, x});
  49.             path[y - 1][x][0] = y;
  50.             path[y - 1][x][1] = x;
  51.         }
  52.         if (grid[y + 1][x]) {
  53.             queue.push({ y + 1, x});
  54.             path[y + 1][x][0] = y;
  55.             path[y + 1][x][1] = x;
  56.         }
  57.         if (grid[y][x - 1]) {
  58.             queue.push({y, x - 1});
  59.             path[y][x - 1][0] = y;
  60.             path[y][x - 1][1] = x;
  61.         }
  62.         if (grid[y][x + 1]) {
  63.             queue.push({y, x + 1});
  64.             path[y][x + 1][0] = y;
  65.             path[y][x + 1][1] = x;
  66.         }
  67.     }
  68.  
  69.     cout << "NO";
  70.  
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement