Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cmath>
- #include<vector>
- #include<queue>
- #include<set>
- #include<cstring>
- #include<iterator>
- using namespace std;
- int i, n, m, x, y, k, start, finish;
- set <int> a[10005];
- char l[105][105];
- int ch;
- queue <int> q;
- int main()
- {
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- cin >> n >> m;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= m; j++)
- cin >> l[i][j];
- for (i = 1; i <= n; i++)
- for (int j = 1; j <= m; j++)
- {
- if (l[i][j] == 'T')
- finish = i * m + j;
- if (l[i][j] == 'S')
- start = i * m + j;
- if ((l[i][j] == '.')||(l[i][j] == 'T')||(l[i][j] == 'S'))
- {
- if (i > 1)
- if ((l[i - 1][j] == '.')||(l[i - 1][j] == 'T')||(l[i - 1][j] == 'S'))
- {
- a[(i - 1) * m + j].insert(i * m + j);
- a[i * m + j].insert((i - 1) * m + j);
- }
- if (i < n)
- if ((l[i + 1][j] == '.')||(l[i + 1][j] == 'T')||(l[i + 1][j] == 'S'))
- {
- a[(i + 1) * m + j].insert(i * m + j);
- a[i * m + j].insert((i + 1) * m + j);
- }
- if (j > 1)
- if ((l[i][j - 1] == '.')||(l[i][j - 1] == 'T')||(l[i][j - 1] == 'S'))
- {
- a[i * m + j - 1].insert(i * m + j);
- a[i * m + j].insert(i * m + j - 1);
- }
- if (j < m)
- if ((l[i][j + 1] == '.')||(l[i][j + 1] == 'T')||(l[i][j + 1] == 'S'))
- {
- a[i * m + j + 1].insert(i * m + j);
- a[i * m + j].insert(i * m + j + 1);
- }
- }
- }
- int b[(n + 1) * (m + 1)], way[(n + 1) * (m + 1)];
- for (i = 0; i < (n + 1) * (m + 1); i++)
- {
- b[i] = 0;
- way[i] = 0;
- }
- k = 1;
- q.push(start);
- while (!q.empty())
- {
- ch = q.front();
- q.pop();
- if (b[ch] == 0)
- {
- b[ch] = k;
- for (auto j = a[ch].begin(); j != a[ch].end(); j++)
- if (b[*j] == 0)
- {
- q.push(*j);
- if (way[*j] != 0)
- way[*j] = min(way[*j], way[ch] + 1);
- else
- way[*j] = way[ch] + 1;
- }
- }
- }
- if (way[finish] == 0)
- {
- cout << -1;
- return 0;
- }
- ch = finish;
- char route[way[ch] + 10];
- for (i = 0; i <= way[ch] + 1; i++)
- route[i] = ' ';
- i = way[finish];
- while(ch != start)
- {
- if (ch - m > 0)
- if ((way[ch] > way[ch - m]) && ((way[ch - m] > 0) || (ch - m == start)))
- {
- route[i] = 'D';
- ch = ch - m;
- i--;
- }
- if (ch + 1 <= n * m)
- if ((way[ch] > way[ch + 1]) && ((way[ch + 1] > 0) || (ch + 1 == start)))
- {
- route[i] = 'L';
- ch = ch + 1;
- i--;
- }
- if (ch - 1 > 0)
- if ((way[ch] > way[ch - 1]) && ((way[ch - 1] > 0) || (ch - 1 == start)))
- {
- route[i] = 'R';
- ch = ch - 1;
- i--;
- }
- if (ch + m <= n * m)
- if ((way[ch] > way[ch + m]) && ((way[ch + m] > 0) || (ch + m == start)))
- {
- route[i] = 'U';
- ch = ch + m;
- i--;
- }
- }
- cout << way[finish] << endl;
- for (i = 1; i <= way[finish]; i++)
- cout << route[i];
- return 0;
- }
- /*
- 5 4
- .S..
- ###.
- T...
- .##.
- ....
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement