Advertisement
Josif_tepe

Untitled

Mar 10th, 2023
760
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.53 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. #include <fstream>
  4. #include <string>
  5. #include <set>
  6. #include <cstring>
  7. #include <queue>
  8. #define ll long long
  9. #define ld long double
  10. #define fi first
  11. #define se second
  12. #define mp make_pair
  13. #define pb push_back
  14. #define eb emplace_back
  15. #define all(x) (x).begin(), (x).end()
  16. #define INF 1e18
  17. #define eps 0.00001
  18. #define le length
  19. #define MOD 1000000007
  20. using namespace std;
  21. ll memo[2005][2005];
  22. int prices[1005];
  23. int pages[1005];
  24. int n;
  25. int x;
  26.  
  27.  
  28. char mat[1005][1005];
  29. int prev_steps[1005][1005];
  30. int main() {
  31. //    ifstream cin ("input.txt");
  32.     int n, m;
  33.     cin >> n >> m;
  34.     int ei, ej, si, sj;
  35.     int di[] = {-1, 1, 0, 0};
  36.     int dj[] = {0, 0, -1, 1};
  37.     for(int i = 0; i < n; i++) {
  38.         for(int j =0 ; j < m; j++) {
  39.             cin >> mat[i][j];
  40.             if(mat[i][j] == 'A') {
  41.                 si = i;
  42.                 sj = j;
  43.             }
  44.             if(mat[i][j] == 'B') {
  45.                 ei = i;
  46.                 ej = j;
  47.             }
  48.         }
  49.     }
  50.     queue<int> q;
  51.     q.push(si);
  52.     q.push(sj);
  53.     q.push(0);
  54.     vector<vector<bool> > visited(n + 1, vector<bool>(m + 1, false));
  55.     visited[si][sj] = true;
  56.     int path = -1;
  57.     while(!q.empty()) {
  58.         int ci = q.front(); q.pop();
  59.         int cj = q.front(); q.pop();
  60.         int dist = q.front(); q.pop();
  61.         if(ci == ei and cj == ej) {
  62.             path = dist;
  63.             break;
  64.         }
  65.         for(int i = 0; i < 4; i++) {
  66.             int ti = ci + di[i];
  67.             int tj = cj + dj[i];
  68.             if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] != '#') {
  69.                 q.push(ti);
  70.                 q.push(tj);
  71.                 q.push(dist + 1);
  72.                 prev_steps[ti][tj] = i;
  73.                 visited[ti][tj] = true;
  74.             }
  75.         }
  76.     }
  77.    
  78.     if(path == -1) {
  79.         cout << "NO";
  80.         return 0;
  81.     }
  82.     cout << "YES\n" << path << endl;
  83.     pair<int, int> S = {si, sj}, E = {ei, ej};
  84.     string res = "";
  85.     while(E != S) {
  86.         int direction = prev_steps[E.first][E.second];
  87.        
  88.         if(direction == 0) {
  89.             res += "U";
  90.         }
  91.         else if(direction == 1) {
  92.             res += "D";
  93.         }
  94.         else if(direction == 2) {
  95.             res += "L";
  96.         }
  97.         else {
  98.             res += "R";
  99.         }
  100.         E = {E.first - di[direction], E.second - dj[direction]};
  101.     }
  102.     reverse(res.begin(), res.end());
  103.     cout << res << endl;
  104.     return 0;
  105. }
  106.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement