Advertisement
Guest User

Untitled

a guest
Feb 17th, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | None | 0 0
  1. #pragma warning(disable : 4996)
  2. #include <iostream>
  3. #include <vector>
  4. #include <queue>
  5. #include <string>
  6.  
  7. using namespace std;
  8.  
  9. void bfs(vector<vector<char>> &mapa, vector<vector<char>> &path, pair<int, int> start)
  10. {
  11.     queue<pair<int, int>> q;
  12.     q.push(start);
  13.     path[start.first][start.second] = 'S';
  14.  
  15.     while (!q.empty())
  16.     {
  17.         pair<int, int> v = q.front();
  18.         q.pop();
  19.  
  20.         if (mapa[v.first - 1][v.second] != '#' && path[v.first - 1][v.second] == '-')
  21.         {
  22.             path[v.first - 1][v.second] = 'U';
  23.             q.push({ v.first - 1, v.second });
  24.         }
  25.         if (mapa[v.first + 1][v.second] != '#' && path[v.first + 1][v.second] == '-')
  26.         {
  27.             path[v.first + 1][v.second] = 'D';
  28.             q.push({ v.first + 1, v.second });
  29.         }
  30.         if (mapa[v.first][v.second - 1] != '#' && path[v.first][v.second - 1] == '-')
  31.         {
  32.             path[v.first][v.second - 1] = 'L';
  33.             q.push({ v.first, v.second - 1 });
  34.         }
  35.         if (mapa[v.first][v.second + 1] != '#' && path[v.first][v.second + 1] == '-')
  36.         {
  37.             path[v.first][v.second + 1] = 'R';
  38.             q.push({ v.first , v.second + 1});
  39.         }
  40.     }
  41. }
  42.  
  43. int main()
  44. {
  45.     //freopen("pathbge1.in", "r", stdin);
  46.     //freopen("pathbge1.out", "w", stdout);
  47.     freopen("input.txt", "r", stdin);
  48.     freopen("output.txt", "w", stdout);
  49.     int n, m;
  50.     cin >> n >> m;
  51.     getchar();
  52.     vector<vector<char>> mapa(n + 2, vector<char>(m + 2, '#'));
  53.     vector<vector<char>> path(n + 2, vector<char>(m + 2, '-'));
  54.  
  55.     pair<int, int> start;
  56.     pair<int, int> finish;
  57.     for (int i = 1; i <= n; i++)
  58.     {
  59.         for (int j = 1; j <= m; j++)
  60.         {
  61.             mapa[i][j] = getchar();
  62.             if (mapa[i][j] == 'S')
  63.                 start = { i,j };
  64.             if (mapa[i][j] == 'T')
  65.                 finish = { i,j };
  66.         }
  67.         getchar();
  68.     }
  69.  
  70.     bfs(mapa, path, start);
  71.     if (path[finish.first][finish.second] == '-')
  72.     {
  73.         cout << "-1";
  74.         return 0;
  75.     }
  76.     else
  77.     {
  78.         string ans;
  79.         pair<int, int> v = finish;
  80.         while (v != start)
  81.         {
  82.             ans += path[v.first][v.second];
  83.             if (path[v.first][v.second] == 'U') {
  84.                 v.first++;
  85.             }
  86.             else if (path[v.first][v.second] == 'D') {
  87.                 v.first--;
  88.             }
  89.             else if (path[v.first][v.second] == 'L') {
  90.                 v.second++;
  91.             }
  92.             else if (path[v.first][v.second] == 'R') {
  93.                 v.second--;
  94.             }
  95.         }
  96.         reverse(ans.begin(), ans.end());
  97.         cout << ans.size() << endl;
  98.         cout << ans;
  99.     }
  100.     return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement