Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma warning(disable : 4996)
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <string>
- using namespace std;
- void bfs(vector<vector<char>> &mapa, vector<vector<char>> &path, pair<int, int> start)
- {
- queue<pair<int, int>> q;
- q.push(start);
- path[start.first][start.second] = 'S';
- while (!q.empty())
- {
- pair<int, int> v = q.front();
- q.pop();
- if (mapa[v.first - 1][v.second] != '#' && path[v.first - 1][v.second] == '-')
- {
- path[v.first - 1][v.second] = 'U';
- q.push({ v.first - 1, v.second });
- }
- if (mapa[v.first + 1][v.second] != '#' && path[v.first + 1][v.second] == '-')
- {
- path[v.first + 1][v.second] = 'D';
- q.push({ v.first + 1, v.second });
- }
- if (mapa[v.first][v.second - 1] != '#' && path[v.first][v.second - 1] == '-')
- {
- path[v.first][v.second - 1] = 'L';
- q.push({ v.first, v.second - 1 });
- }
- if (mapa[v.first][v.second + 1] != '#' && path[v.first][v.second + 1] == '-')
- {
- path[v.first][v.second + 1] = 'R';
- q.push({ v.first , v.second + 1});
- }
- }
- }
- int main()
- {
- //freopen("pathbge1.in", "r", stdin);
- //freopen("pathbge1.out", "w", stdout);
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n, m;
- cin >> n >> m;
- getchar();
- vector<vector<char>> mapa(n + 2, vector<char>(m + 2, '#'));
- vector<vector<char>> path(n + 2, vector<char>(m + 2, '-'));
- pair<int, int> start;
- pair<int, int> finish;
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= m; j++)
- {
- mapa[i][j] = getchar();
- if (mapa[i][j] == 'S')
- start = { i,j };
- if (mapa[i][j] == 'T')
- finish = { i,j };
- }
- getchar();
- }
- bfs(mapa, path, start);
- if (path[finish.first][finish.second] == '-')
- {
- cout << "-1";
- return 0;
- }
- else
- {
- string ans;
- pair<int, int> v = finish;
- while (v != start)
- {
- ans += path[v.first][v.second];
- if (path[v.first][v.second] == 'U') {
- v.first++;
- }
- else if (path[v.first][v.second] == 'D') {
- v.first--;
- }
- else if (path[v.first][v.second] == 'L') {
- v.second++;
- }
- else if (path[v.first][v.second] == 'R') {
- v.second--;
- }
- }
- reverse(ans.begin(), ans.end());
- cout << ans.size() << endl;
- cout << ans;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement