Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2020
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.54 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. void f(queue<pair<int, int>>& s, vector<vector<pair<int, int>>>& j, vector<vector<int>>& p, pair<int, int>& a, pair<int, int>& b, int o, int d)
  9. {
  10. if (b.first == o && b.second == d)
  11. {
  12. }
  13. else if (p[b.first][b.second] == 0)
  14. {
  15. s.push(b);
  16. p[b.first][b.second] = p[a.first][a.second] + 1;
  17. j[b.first][b.second] = a;
  18. }
  19. }
  20.  
  21. void func(queue<pair<int, int>>& s, vector<vector<pair<int, int>>>& j, vector<vector<int>>& p, pair<int, int>& a, int o, int d)
  22. {
  23. pair<int, int> b;
  24.  
  25. b.first = a.first + 1;
  26. b.second = a.second;
  27. if (b.first < p.size())
  28. f(s, j, p, a, b, o, d);
  29.  
  30. b.first = a.first - 1;
  31. b.second = a.second;
  32. if (b.first >= 0)
  33. f(s, j, p, a, b, o, d);
  34.  
  35. b.first = a.first;
  36. b.second = a.second + 1;
  37. if (b.second < p[b.first].size())
  38. f(s, j, p, a, b, o, d);
  39.  
  40. b.first = a.first;
  41. b.second = a.second - 1;
  42. if (b.second >= 0)
  43. f(s, j, p, a, b, o, d);
  44.  
  45. }
  46.  
  47.  
  48.  
  49. int main()
  50. {
  51. ifstream fin("maze.in");
  52. ofstream fout("maze.out");
  53.  
  54. vector<vector<int>> labir;
  55. vector<vector<pair<int, int>>> predki;
  56.  
  57. int M, N;
  58. fin >> M >> N;
  59. labir.resize(M);
  60. predki.resize(M);
  61. for (int i = 0; i < M; i++)
  62. {
  63. labir[i].resize(N);
  64. predki[i].resize(N);
  65. }
  66.  
  67. pair<int, int> begin;
  68. pair<int, int> end;
  69. fin >> begin.first >> begin.second;
  70. fin >> end.first >> end.second;
  71. end.first = end.first - 1;
  72. end.second = end.second - 1;
  73. begin.first = begin.first - 1;
  74. begin.second = begin.second - 1;
  75. for (int i = 0; i < M; i++)
  76. {
  77. for (int j = 0; j < N; j++)
  78. {
  79. int b;
  80. fin >> b;
  81. if (b == 1)
  82. {
  83. labir[i][j] = 0;
  84. }
  85. else
  86. {
  87. labir[i][j] = -1;
  88. }
  89. }
  90. }
  91. queue<pair<int, int>> obhod;
  92. obhod.push(begin);
  93.  
  94. while (labir[end.first][end.second] == 0 && !obhod.empty())
  95. {
  96. pair<int, int> t;
  97. t = obhod.front();
  98. obhod.pop();
  99.  
  100. func(obhod, predki, labir, t, begin.first, begin.second);
  101. }
  102.  
  103. if (labir[end.first][end.second] == 0)
  104. {
  105. fout << -1;
  106. }
  107. else
  108. {
  109. fout << labir[end.first][end.second] << endl;
  110. pair<int, int> t1 = end;
  111. pair<int, int> t2;
  112. deque<pair <int, int>> way;
  113. for (int i = 0; i < labir[end.first][end.second]; i++)
  114. {
  115. t2 = predki[t1.first][t1.second];
  116. t1 = t2;
  117. way.push_front(t2);
  118. }
  119. for (int i = 0; i < labir[end.first][end.second]; i++)
  120. {
  121. fout << way.front().first + 1 << " " << way.front().second + 1 << endl;
  122. way.pop_front();
  123. }
  124. fout << end.first + 1 << " " << end.second + 1 << endl;
  125. }
  126.  
  127.  
  128. return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement