Advertisement
aayyk

Untitled

Nov 22nd, 2019
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.15 KB | None | 0 0
  1. ο»Ώ#include <iostream>
  2. #include <iomanip>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #include <stack>
  8. #include <climits>
  9. #include <string>
  10. #include <set>
  11. #include <cmath>
  12. #include <map>
  13. #include <unordered_map>
  14. #include <numeric>
  15. #include <random>
  16. #include <memory>
  17. #include <chrono>
  18. #include <iterator>
  19. #include <functional>
  20. #include <unordered_set>
  21. #include <cassert>
  22. #ifdef LOCAL
  23. #include "debug.h"
  24. #else
  25. #define debug(x...)
  26. #endif
  27. //#pragma GCC optimize("Ofast")
  28. //#define int ll
  29.  
  30.  
  31.  
  32. using namespace std;
  33. typedef long long ll;
  34. typedef long double ld;
  35. typedef pair < int, int > pii;
  36. typedef pair < ll, ll > pll;
  37. #define sz(x) int((x).size())
  38.  
  39. #ifndef LOCAL
  40. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  41. #else
  42. mt19937 rng(228);
  43. #endif
  44.  
  45. const int N = 1e3 + 7;
  46. const int inf = INT_MAX / 2;
  47. const ll INF = LLONG_MAX / 3;
  48. const int MOD = 1e9 + 7;
  49. const double eps = 1e-6;
  50. const string cars[] = {"πŸš—", "πŸš•", "πŸš™"};
  51.  
  52. struct Node {
  53.     int x, y, l, w;
  54.  
  55.     bool check() {
  56.         return (--l) <= 0;
  57.     }
  58. };
  59.  
  60. int n, m, sx, sy, fx, fy, d[N][N];
  61. char a[N][N];
  62. short used[N][N];
  63. queue < Node > q;
  64. pii p[N][N];
  65.  
  66. void go(int x, int y, int px, int py) {
  67.     if (x >= 1 && x <= n && y >= 1 && y <= m && !used[x][y] && a[x][y] != '#') {
  68.         used[x][y] = 1;
  69.         if (a[x][y] == '.') {
  70.             q.push({ x, y, 1, d[px][py] + 1 });
  71.             p[x][y] = { px, py };
  72.         }
  73.         else {
  74.             q.push({ x, y, 2, d[px][py] + 2 });
  75.             p[x][y] = { px, py };
  76.         }
  77.     }
  78. }
  79.  
  80. void bfs() {
  81.     q.push({ sx, sy, 0, 0 });
  82.     used[sx][sy] = 1;
  83.  
  84.     while (!q.empty()) {
  85.         auto u = q.front();
  86.         q.pop();
  87.  
  88.         if (u.check()) {
  89.             d[u.x][u.y] = u.w;
  90.  
  91.             go(u.x + 1, u.y, u.x, u.y);
  92.             go(u.x - 1, u.y, u.x, u.y);
  93.             go(u.x, u.y + 1, u.x, u.y);
  94.             go(u.x, u.y - 1, u.x, u.y);
  95.         }
  96.         else {
  97.             q.push(u);
  98.         }
  99.     }
  100. }
  101.  
  102. signed main() {
  103. #ifdef LOCAL
  104.     freopen("input.txt", "r", stdin);
  105.     freopen("output.txt", "w", stdout);
  106. #endif
  107.     cout << fixed << setprecision(4);
  108.     ios::sync_with_stdio(false);
  109.     cin.tie();
  110.     cout.tie();
  111.  
  112.     cin >> n >> m >> sx >> sy >> fx >> fy;
  113.  
  114.     for (int i = 1; i <= n; i++) {
  115.         for (int j = 1; j <= m; j++) {
  116.             cin >> a[i][j];
  117.         }
  118.     }
  119.  
  120.     bfs();
  121.  
  122.     if (!used[fx][fy]) {
  123.         return cout << "-1", 0;
  124.     }
  125.  
  126.     cout << d[fx][fy] << "\n";
  127.    
  128.     vector < pii > path;
  129.     for (pii i = { fx, fy }; i != pii{ sx, sy }; i = p[i.first][i.second]) {
  130.         path.push_back(i);
  131.     }
  132.     path.push_back({ sx, sy });
  133.     reverse(path.begin(), path.end());
  134.  
  135.     for (int i = 1; i < sz(path); i++) {
  136.         int dx = path[i].first - path[i - 1].first;
  137.         int dy = path[i].second - path[i - 1].second;
  138.  
  139.         if (dx == 1) {
  140.             cout << 'S';
  141.         }
  142.         else if (dx == -1) {
  143.             cout << 'N';
  144.         }
  145.         else if (dy == 1) {
  146.             cout << 'E';
  147.         }
  148.         else {
  149.             cout << 'W';
  150.         }
  151.     }
  152.  
  153.     return 0;
  154. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement