Advertisement
HabKaffee

Untitled

Oct 3rd, 2021
1,151
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <utility>
  5. #include <climits>
  6. #include <string>
  7. #include <queue>
  8. #include <algorithm>
  9.  
  10.  
  11. int main () {
  12.     std::vector<std::pair<int, int>> deltas = {{-1, -2}, {-1, 2}, {1, -2}, {1, 2},
  13.                                                {-2, 1}, {-2, -1}, {2, 1}, {2, -1}};
  14.     std::ifstream input("../input.txt");
  15.     int n = 0, m = 0;
  16.     input >> n >> m;
  17.     std::vector<std::vector<long>> field(n, std::vector<long>(m, INT_MAX));
  18.     for (size_t i = 0; i < n; ++i) {
  19.         std::string tmp;
  20.         input >> tmp;
  21.         for (size_t j = 0; j < m; ++j) {
  22.             if (tmp[j] == 'x') {
  23.                 field[i][j] = -1;
  24.             }
  25.         }
  26.     }
  27.     for (size_t i = 0; i < n; ++i) {
  28.         for (size_t j = 0; j < m; ++j) {
  29.             std::cout << ((field[i][j] == -1) ? 'x' : '-');
  30.         }
  31.         std::cout << std::endl;
  32.     }
  33.     std::pair<long, long> startPos, finishPos;
  34.     input >> startPos.first >> startPos.second >> finishPos.first >> finishPos.second;
  35.     //  Checking if start and finish are same
  36.     if ((startPos == finishPos)) {
  37.         std::cout << 0 << std::endl;
  38.         return 0;
  39.     }
  40.     if (field[finishPos.first][finishPos.second] == -1) {
  41.         std::cout << -1 << std::endl;
  42.         return 0;
  43.     }
  44.     field[startPos.first][startPos.second] = 0;
  45.     std::vector<std::pair<long, long>> path;
  46.     std::queue<std::pair<long, long>> toVisit;
  47.     std::pair<long, long> currPos = startPos;
  48.     toVisit.push(currPos);
  49.     while(!toVisit.empty()) {
  50.         currPos = toVisit.front();
  51.         toVisit.pop();
  52. //        if ((field[currPos.first][currPos.second] != INT_MAX) && (field[currPos.first][currPos.second] > field[path.back().first][path.back().second])) {
  53. //            path.push_back(currPos);
  54. //        }
  55.         if (currPos == finishPos) {
  56.             field[finishPos.first][finishPos.second] = field[path.back().first][path.back().second] + 1;
  57.             break;
  58.         }
  59.         for (size_t i = currPos.first; i < n - 2; ++i) {
  60.             for (size_t j = currPos.second; j < m - 2; ++j) {
  61.                 if ((i + deltas[0].first >= 0) && (j + deltas[0].second >= 0)) {
  62.                     if (field[i + deltas[0].first][j + deltas[0].second] == INT_MAX) {
  63.                         toVisit.push({i + deltas[0].first, j + deltas[0].second});
  64.                         field[i + deltas[0].first][j + deltas[0].second] = field[currPos.first][currPos.second] + 1;
  65.                     }
  66.                 }
  67.                 if ((i + deltas[1].first >= 0) && (j + deltas[1].second < m)) {
  68.                     if (field[i + deltas[1].first][j + deltas[1].second] == INT_MAX) {
  69.                         toVisit.push({i + deltas[1].first, j + deltas[1].second});
  70.                         field[i + deltas[1].first][j + deltas[1].second] = field[currPos.first][currPos.second] + 1;
  71.                     }
  72.                 }
  73.                 if ((i + deltas[2].first < n) && (j + deltas[2].second >= 0)) {
  74.                     if (field[i + deltas[2].first][j + deltas[2].second] == INT_MAX) {
  75.                         toVisit.push({i + deltas[2].first, j + deltas[2].second});
  76.                         field[i + deltas[2].first][j + deltas[2].second] = field[currPos.first][currPos.second] + 1;
  77.                     }
  78.                 }
  79.                 if ((i + deltas[3].first < n) && (j + deltas[3].second < m)) {
  80.                     if (field[i + deltas[3].first][j + deltas[3].second] == INT_MAX) {
  81.                         toVisit.push({i + deltas[3].first, j + deltas[3].second});
  82.                         field[i + deltas[3].first][j + deltas[3].second] = field[currPos.first][currPos.second] + 1;
  83.                     }
  84.                 }
  85.                 if ((i + deltas[4].first >= 0) && (j + deltas[4].second < m)) {
  86.                     if (field[i + deltas[4].first][j + deltas[4].second] == INT_MAX) {
  87.                         toVisit.push({i + deltas[4].first, j + deltas[4].second});
  88.                         field[i + deltas[4].first][j + deltas[4].second] = field[currPos.first][currPos.second] + 1;
  89.                     }
  90.                 }
  91.                 if ((i + deltas[5].first >= 0) && (j + deltas[5].second >= 0)) {
  92.                     if (field[i + deltas[5].first][j + deltas[5].second] == INT_MAX) {
  93.                         toVisit.push({i + deltas[5].first, j + deltas[5].second});
  94.                         field[i + deltas[5].first][j + deltas[5].second] = field[currPos.first][currPos.second] + 1;
  95.                     }
  96.                 }
  97.                 if ((i + deltas[6].first < n) && (j + deltas[6].second < m)) {
  98.                     if (field[i + deltas[6].first][j + deltas[6].second] == INT_MAX) {
  99.                         toVisit.push({i + deltas[6].first, j + deltas[6].second});
  100.                         field[i + deltas[6].first][j + deltas[6].second] = field[currPos.first][currPos.second] + 1;
  101.                     }
  102.                 }
  103.                 if ((i + deltas[7].first < n) && (j + deltas[7].second >= 0)) {
  104.                     if (field[i + deltas[7].first][j + deltas[7].second] == INT_MAX) {
  105.                         toVisit.push({i + deltas[7].first, j + deltas[7].second});
  106.                         field[i + deltas[7].first][j + deltas[7].second] = field[currPos.first][currPos.second] + 1;
  107.                     }
  108.                 }
  109.             }
  110.         }
  111.     }
  112.     if (std::find(path.begin(), path.end(), finishPos) == path.end()) {
  113.         std::cout << -1 << std::endl;
  114.     } else {
  115.         std::cout << path.size() - 1 << std::endl;
  116.         for (auto obj: path) {
  117.             std::cout << obj.first << " " << obj.second << std::endl;
  118.         }
  119.     }
  120.     return 0;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement