Advertisement
Guest User

EDITTED

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