Advertisement
Guest User

Лабиринт (обход в ширину)

a guest
May 31st, 2022
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <fstream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <set>
  7. #include <queue>
  8. #include <cstring>
  9.  
  10. using namespace std;
  11.  
  12.  
  13. const int INF = 100000;
  14.  
  15. int m, n;
  16. int i, j;
  17. vector<vector<char>> a;
  18. vector<vector<int> > res;
  19. bool check(int ii, int jj){ // проверка на границы
  20. if(ii < 0)
  21. return 0;
  22. if(ii >= m)
  23. return 0;
  24. if(jj < 0)
  25. return 0;
  26. if(jj >= n)
  27. return 0;
  28. if(a[ii][jj] == 'X')
  29. return 0;
  30. if(res[ii][jj] < res[i][j])
  31. return 0;
  32. return 1;
  33. }
  34. int main() {
  35. freopen("input.txt", "r", stdin);
  36. freopen("output.txt", "w", stdout);
  37. cin >> m >> n;
  38. a.resize(100, vector<char> (100));
  39. res.resize(100, vector<int> (100, 100000));
  40. int idxi = 101, idxj;
  41. queue<pair<int, int>> q;
  42. for(int i = 0; i < m; i++){
  43. for(int j = 0; j < n; ++j){
  44. cin >> a[i][j];
  45. if(a[i][j] == 'S'){
  46. q.push(make_pair(i, j));
  47. res[i][j] = 0;
  48. }
  49. if(a[i][j] == 'F'){
  50. idxi = i;
  51. idxj = j;
  52. }
  53. }
  54. }
  55.  
  56. while(q.size()){ // обход в ширину
  57. auto t = q.front();
  58. i = t.first;
  59. j = t.second;
  60. if(check(i, j - 1)){
  61. res[i][j - 1] = res[i][j] + 1;
  62. q.push(make_pair(i, j - 1));
  63. }
  64. if(check(i, j + 1)){
  65. res[i][j + 1] = res[i][j] + 1;
  66. q.push(make_pair(i, j + 1));
  67. }
  68. if(check(i + 1, j)){
  69. res[i + 1][j] = res[i][j] + 1;
  70. q.push(make_pair(i + 1, j));
  71. }
  72. if(check(i - 1, j)){
  73. res[i - 1][j] = res[i][j] + 1;
  74. q.push(make_pair(i - 1, j));
  75. }
  76. q.pop();
  77. }
  78. if(res[idxi][idxj] == 100000){
  79. cout << -1;
  80. }
  81. else{
  82. cout << res[idxi][idxj];
  83. }
  84.  
  85. return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement