Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.15 KB | None | 0 0
  1. #include<iostream>
  2. #include<cmath>
  3. #include<vector>
  4. #include<queue>
  5. #include<set>
  6. #include<cstring>
  7. #include<iterator>
  8. using namespace std;
  9. int i, n, m, x, y, k, start, finish;
  10. set <int> a[10005];
  11. char l[105][105];
  12. int ch;
  13. queue <int> q;
  14. int main()
  15. {
  16. // freopen("input.txt", "r", stdin);
  17. // freopen("output.txt", "w", stdout);
  18. cin >> n >> m;
  19. for (int i = 1; i <= n; i++)
  20. for (int j = 1; j <= m; j++)
  21. cin >> l[i][j];
  22. for (i = 1; i <= n; i++)
  23. for (int j = 1; j <= m; j++)
  24. {
  25. if (l[i][j] == 'T')
  26. finish = i * m + j;
  27. if (l[i][j] == 'S')
  28. start = i * m + j;
  29. if ((l[i][j] == '.')||(l[i][j] == 'T')||(l[i][j] == 'S'))
  30. {
  31. if (i > 1)
  32. if ((l[i - 1][j] == '.')||(l[i - 1][j] == 'T')||(l[i - 1][j] == 'S'))
  33. {
  34. a[(i - 1) * m + j].insert(i * m + j);
  35. a[i * m + j].insert((i - 1) * m + j);
  36. }
  37. if (i < n)
  38. if ((l[i + 1][j] == '.')||(l[i + 1][j] == 'T')||(l[i + 1][j] == 'S'))
  39. {
  40. a[(i + 1) * m + j].insert(i * m + j);
  41. a[i * m + j].insert((i + 1) * m + j);
  42. }
  43. if (j > 1)
  44. if ((l[i][j - 1] == '.')||(l[i][j - 1] == 'T')||(l[i][j - 1] == 'S'))
  45. {
  46. a[i * m + j - 1].insert(i * m + j);
  47. a[i * m + j].insert(i * m + j - 1);
  48. }
  49. if (j < m)
  50. if ((l[i][j + 1] == '.')||(l[i][j + 1] == 'T')||(l[i][j + 1] == 'S'))
  51. {
  52. a[i * m + j + 1].insert(i * m + j);
  53. a[i * m + j].insert(i * m + j + 1);
  54. }
  55. }
  56. }
  57. int b[(n + 1) * (m + 1)], way[(n + 1) * (m + 1)];
  58. for (i = 0; i < (n + 1) * (m + 1); i++)
  59. {
  60. b[i] = 0;
  61. way[i] = 0;
  62. }
  63. k = 1;
  64. q.push(start);
  65. while (!q.empty())
  66. {
  67. ch = q.front();
  68. q.pop();
  69. if (b[ch] == 0)
  70. {
  71. b[ch] = k;
  72. for (auto j = a[ch].begin(); j != a[ch].end(); j++)
  73. if (b[*j] == 0)
  74. {
  75. q.push(*j);
  76. if (way[*j] != 0)
  77. way[*j] = min(way[*j], way[ch] + 1);
  78. else
  79. way[*j] = way[ch] + 1;
  80. }
  81. }
  82. }
  83. if (way[finish] == 0)
  84. {
  85. cout << -1;
  86. return 0;
  87. }
  88. ch = finish;
  89. char route[way[ch] + 10];
  90. for (i = 0; i <= way[ch] + 1; i++)
  91. route[i] = ' ';
  92. i = way[finish];
  93. while(ch != start)
  94. {
  95. if (ch - m > 0)
  96. if ((way[ch] > way[ch - m]) && ((way[ch - m] > 0) || (ch - m == start)))
  97. {
  98. route[i] = 'D';
  99. ch = ch - m;
  100. i--;
  101. }
  102. if (ch + 1 <= n * m)
  103. if ((way[ch] > way[ch + 1]) && ((way[ch + 1] > 0) || (ch + 1 == start)))
  104. {
  105. route[i] = 'L';
  106. ch = ch + 1;
  107. i--;
  108. }
  109. if (ch - 1 > 0)
  110. if ((way[ch] > way[ch - 1]) && ((way[ch - 1] > 0) || (ch - 1 == start)))
  111. {
  112. route[i] = 'R';
  113. ch = ch - 1;
  114. i--;
  115. }
  116. if (ch + m <= n * m)
  117. if ((way[ch] > way[ch + m]) && ((way[ch + m] > 0) || (ch + m == start)))
  118. {
  119. route[i] = 'U';
  120. ch = ch + m;
  121. i--;
  122. }
  123. }
  124. cout << way[finish] << endl;
  125. for (i = 1; i <= way[finish]; i++)
  126. cout << route[i];
  127. return 0;
  128. }
  129. /*
  130. 5 4
  131. .S..
  132. ###.
  133. T...
  134. .##.
  135. ....
  136. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement