Advertisement
Guest User

Untitled

a guest
Feb 19th, 2020
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.30 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n, m;
  4. char c;
  5. vector<pair<int, int>> p;
  6. vector<bool> checked;
  7. vector<char> point, dist;
  8. void bfs( int i ){
  9. p[i].first = i;
  10. p[i].second = 0;
  11. queue<int> q;
  12. q.push( i );
  13. while( !q.empty() ){
  14. int E = q.front();
  15. q.pop();
  16. if( point[E] == 'T' )
  17. break;
  18. if( !checked[E] ){
  19. checked[E] = true;
  20. if( point[E - 1] != '#' && E % m != 0 && !checked[E - 1] ){
  21. p[E - 1].first = E;
  22. p[E - 1].second = p[E].second + 1;
  23. dist[E - 1] = 'L';
  24. q.push( E - 1 );
  25. }
  26. if( point[E + 1] != '#' && ( E + 1 ) % m != 0 && !checked[E + 1] ){
  27. p[E + 1].first = E;
  28. p[E + 1].second = p[E].second + 1;
  29. dist[E + 1] = 'R';
  30. q.push( E + 1 );
  31. }
  32. if( point[E - m] != '#' && E + 1 > m && !checked[E - m] ){
  33. p[E - m].first = E;
  34. p[E - m].second = p[E].second + 1;
  35. dist[E - m] = 'U';
  36. q.push( E - m );
  37. }
  38. if( point[E + m] != '#' && E + 1 <= m * ( n - 1 ) && !checked[E + m] ){
  39. p[E + m].first = E;
  40. p[E + m].second = p[E].second + 1;
  41. dist[E + m] = 'D';
  42. q.push( E + m );
  43. }
  44. }
  45. }
  46. }
  47. void distance( int i ){
  48. if( p[i].first != i )
  49. distance( p[i].first );
  50. if( dist[i] != 'r' )
  51. cout << dist[i];
  52. }
  53. int main(){
  54. ios_base::sync_with_stdio(false);
  55. cin.tie(NULL);
  56. //freopen( "input.txt", "r", stdin );
  57. //freopen( "output.txt", "w", stdout);
  58. cin >> n >> m;
  59. if( n == 1 && m == 1 ){
  60. cout << -1;
  61. return 0;
  62. }
  63. int s, f;
  64. for( int i = 0; i < n * m; i++ ){
  65. cin >> c;
  66. if( c == 'S' )
  67. s = i;
  68. if( c == 'T' )
  69. f = i;
  70. point.push_back( c );
  71. }
  72. for( int i = 0; i < n * m; i++ ){
  73. checked.push_back( false );
  74. dist.push_back( 'r' );
  75. p.push_back( { 0, 0 } );
  76. }
  77. bfs( s );
  78. if( p[f].second == 0 ){
  79. cout << -1;
  80. return 0;
  81. }
  82. cout << p[f].second << endl;
  83. distance( f );
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement