Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2019
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.75 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <string>
  6. #include <string.h>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <math.h>
  11. #include <cmath>
  12. #include <map>
  13. #include <set>
  14. #include <cstdlib>
  15. #include <utility>
  16. #include <iomanip>
  17.  
  18. using namespace std;
  19.  
  20. typedef long long ll;
  21. typedef long double ld;
  22. typedef string st;
  23. typedef pair<int, int> pii;
  24. typedef vector <pair<int, int>> vpii;
  25.  
  26. struct ver {
  27. int xv, yv;
  28. bool h;
  29. };
  30. const int INF = 1e5;
  31. const int SIZE = 501;
  32. char g[SIZE][SIZE];
  33. int used[SIZE][SIZE], dist[SIZE][SIZE], n, m;
  34. pii par[SIZE][SIZE];
  35. deque<ver> q;
  36.  
  37.  
  38.  
  39. bool exist(int x1, int y1) {
  40. return !(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m);
  41. }
  42.  
  43. int dx[] = { 1, -1, 0, 0 };
  44. int dy[] = { 0, 0, -1, 1 };
  45. int size_d = 4;
  46.  
  47. int main() {
  48. //setlocale(LC_ALL, "Russian");
  49. //freopen("INPUT.TXT", "r", stdin);
  50. //freopen("OUTPUT.TXT", "w", stdout);
  51. ios_base::sync_with_stdio(false);
  52. cin.tie(0);
  53. cin >> n >> m;
  54. int xc, yc;
  55. int xl, yl;
  56. for (int i = 0; i < n; ++i) {
  57. for (int j = 0; j < m; ++j) {
  58. cin >> g[i][j];
  59. if (g[i][j] == 'F') {
  60. xc = i;
  61. yc = j;
  62. }
  63. if (g[i][j] == 'S') {
  64. xl = i;
  65. yl = j;
  66. }
  67. if (g[i][j] == 'P') used[i][j] = 1;
  68. dist[i][j] = INF;
  69. }
  70. }
  71. used[xc][yc] = 1;
  72. dist[xc][yc] = 0;
  73. //par[xc][yc] = make_pair(-1, -1);
  74. q.push_back({ xc, yc, 1 });
  75. while (!q.empty()) {
  76. int x = q.front().xv;
  77. int y = q.front().yv;
  78. bool h = q.front().h;
  79. q.pop_front();
  80. if (h) {
  81. int tox = x;
  82. for (int toy = y + 1; toy < n; toy++) {
  83. if (g[tox][toy] == 'P') break;
  84. else if (exist(tox, toy) && !used[tox][toy]) {
  85. used[tox][toy] = 1;
  86. dist[tox][toy] = dist[x][y] + 1;
  87. par[tox][toy] = make_pair(x, y);
  88. q.push_back({ tox, toy, 0 });
  89. }
  90. }
  91. for (int toy = 0; toy < y; toy++) {
  92. if (g[tox][toy] == 'P') break;
  93. else if (exist(tox, toy) && !used[tox][toy]) {
  94. used[tox][toy] = 1;
  95. dist[tox][toy] = dist[x][y] + 1;
  96. par[tox][toy] = make_pair(x, y);
  97. q.push_front({ tox, toy, 0 });
  98. }
  99. }
  100. }
  101. if(!h || x==xc && y==yc) {
  102. int toy = y;
  103. for (int tox = x + 1; tox < m; tox++) {
  104. if (g[tox][toy] == 'P') break;
  105. else if (exist(tox, toy) && !used[tox][toy]) {
  106. used[tox][toy] = 1;
  107. dist[tox][toy] = dist[x][y] + 1;
  108. par[tox][toy] = make_pair(x, y);
  109. q.push_back({ tox, toy, 1 });
  110. }
  111. }
  112. for (int tox = 0; tox < x; tox++) {
  113. if (g[tox][toy] == 'P') break;
  114. else if (exist(tox, toy) && !used[tox][toy]) {
  115. used[tox][toy] = 1;
  116. dist[tox][toy] = dist[x][y] + 1;
  117. par[tox][toy] = make_pair(x, y);
  118. q.push_front({ tox, toy, 1 });
  119. }
  120. }
  121. }
  122. }
  123. cout << dist[xl][yl];
  124. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement