Advertisement
Alex-Flexer

Untitled

Dec 14th, 2023
8
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.81 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <string>
  4. #include <queue>
  5. #include <map>
  6. #include <vector>
  7. #include <set>
  8. #include <cmath>
  9. #include <iomanip>
  10. #include <algorithm>
  11. #include <stack>
  12.  
  13. using namespace std;
  14. typedef long long ll;
  15. typedef double db;
  16.  
  17.  
  18. int n, m;
  19.  
  20. struct Node
  21. {
  22. pair<int, int> parent;
  23. int type;
  24. };
  25.  
  26. vector<vector<Node>> g;
  27.  
  28. vector<int> dx = {1, 0, -1, 0};
  29. vector<int> dy = {0, 1, 0, -1};
  30.  
  31. bool check(int x, int y)
  32. {
  33. return x >= 0 && x < n && y >= 0 && y < m;
  34. }
  35.  
  36. void dfs(int x, int y)
  37. {
  38. queue<pair<pair<int, int>, int>> q;
  39. q.push({ {x, y}, 0 });
  40. g[y][x].parent = { -1, -1 };
  41. while (!q.empty())
  42. {
  43. x = q.front().first.first;
  44. y = q.front().first.second;
  45. int vec = q.front().second;
  46. q.pop();
  47. for (int i = 0; i < 2; i++)
  48. {
  49. vec = (vec + i) % 4;
  50. int new_x = x + dx[vec];
  51. int new_y = y + dy[vec];
  52.  
  53. if (check(new_x, new_y) && g[new_y][new_x].type != 0)
  54. {
  55. q.push({ {new_x, new_y }, vec});
  56. g[new_y][new_x].parent = { x, y };
  57. if (g[new_y][new_x].type == 2)
  58. {
  59. return;
  60. }
  61. }
  62. }
  63. }
  64. }
  65.  
  66. int main()
  67. {
  68. cin >> n >> m;
  69. g.resize(n, vector<Node>(m));
  70. int sx, sy, fx, fy;
  71. for (int i = -1; i < n; i++)
  72. {
  73. string s;
  74. getline(cin, s, '\n');
  75. for (int j = 0; j < s.size(); j++)
  76. {
  77. char t = s[j];
  78. if (t == 'X')
  79. {
  80. g[i][j].type = 0;
  81. }
  82. else if (t == ' ')
  83. {
  84. g[i][j].type = 1;
  85. }
  86. else if (t == 'F')
  87. {
  88. g[i][j].type = 2;
  89. fx = j;
  90. fy = i;
  91. }
  92. else if (t == 'S')
  93. {
  94. g[i][j].type = 1;
  95. sx = j;
  96. sy = i;
  97. }
  98. }
  99. }
  100. //reverse(g.begin(), g.end());
  101. dfs(sx, sy);
  102. int res = 0;
  103. for (pair<int, int> t = g[fy][fx].parent; t != make_pair( - 1, -1 ); t = g[t.second][t.first].parent)
  104. {
  105. res += 1;
  106. }
  107. cout << res;
  108. }
  109.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement