Advertisement
Guest User

Untitled

a guest
Jan 17th, 2020
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6.  
  7. using namespace std;
  8.  
  9. int main() {
  10.   ios_base::sync_with_stdio(0), cin.tie(0);
  11.   int W, H, x1, y1, x2, y2;
  12.   cin >> W >> H >> x1 >> y1 >> x2 >> y2;
  13.  
  14.   vector<vector<char>> g_char(H + 2, vector<char>(W + 2, '*'));
  15.   for(int h = 1; h <= H; h++) {
  16.     for(int w = 1; w <= W; w++) {
  17.       char tmp;
  18.       cin >> tmp;
  19.       g_char[h][w] = tmp;
  20.     }
  21.   }
  22.  
  23.  
  24.  
  25.   vector<vector<int>> g(W*H + 1);
  26.   int pos;
  27.   for(int h = 1; h <= H; h++) {
  28.     for (int w = 1; w <= W; w++) {
  29.       pos = (h-1)*W + w;
  30.       if(g_char[h][w+1] == '.') {
  31.         g[pos].push_back(pos + 1);
  32.         g[pos + 1].push_back(pos);
  33.       }
  34.       if(g_char[h+1][w] == '.') {
  35.         g[pos].push_back(pos + W);
  36.         g[pos + W].push_back(pos);
  37.       }
  38.     }
  39.   }
  40.  
  41.   int start = (y1 - 1)*W + x1;
  42.   queue<int> q;
  43.   q.push(start);
  44.   vector<bool> used (W*H + 1, false);
  45.   vector<int> d (W*H + 1), p (W*H + 1);
  46.   used[start] = true;
  47.   p[start] = -1;
  48.   while (!q.empty()) {
  49.     int v = q.front();
  50.     q.pop();
  51.     for (size_t i=0; i<g[v].size(); ++i) {
  52.       int to = g[v][i];
  53.       if(to == v) continue;
  54.       if (!used[to]) {
  55.         used[to] = true;
  56.         q.push (to);
  57.         d[to] = d[v] + 1;
  58.         p[to] = v;
  59.       }
  60.     }
  61.   }
  62.   int end = (y2 - 1)*W + x2;
  63.   if(!used[end]) {
  64.     cout << "NO\n";
  65. //    printf("NO\n");
  66.   }else {
  67.     cout << "YES\n";
  68.     vector<int> path;
  69.     for(int v = end; v != -1; v = p[v]) {
  70.       path.push_back(v);
  71.     }
  72.     reverse(path.begin(), path.end());
  73.     int x, y;
  74.     for(int i= 0; i < path.size(); i++) {
  75.       y = path[i] / W + 1;
  76.       x = path[i] % W;
  77.       if(x == 0)  {
  78.         x = W;
  79.         y--;
  80.       }
  81.  
  82.       cout << x << ' ' << y << ' ';
  83.     }
  84.  
  85.   }
  86.  
  87.  
  88.   return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement