Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <utility>
- #include <climits>
- #include <string>
- #include <queue>
- #include <algorithm>
- int main () {
- std::vector<std::pair<int, int>> deltas = {{-1, -2}, {-1, 2}, {1, -2}, {1, 2},
- {-2, 1}, {-2, -1}, {2, 1}, {2, -1}};
- std::ifstream input("../input.txt");
- int n = 0, m = 0;
- input >> n >> m;
- std::vector<std::vector<long>> field(n, std::vector<long>(m, INT_MAX));
- for (size_t i = 0; i < n; ++i) {
- std::string tmp;
- input >> tmp;
- for (size_t j = 0; j < m; ++j) {
- if (tmp[j] == 'x') {
- field[i][j] = -1;
- }
- }
- }
- for (size_t i = 0; i < n; ++i) {
- for (size_t j = 0; j < m; ++j) {
- std::cout << ((field[i][j] == -1) ? 'x' : '-');
- }
- std::cout << std::endl;
- }
- std::pair<long, long> startPos, finishPos;
- input >> startPos.first >> startPos.second >> finishPos.first >> finishPos.second;
- // Checking if start and finish are same
- if ((startPos == finishPos)) {
- std::cout << 0 << std::endl;
- return 0;
- }
- if (field[finishPos.first][finishPos.second] == -1) {
- std::cout << -1 << std::endl;
- return 0;
- }
- field[startPos.first][startPos.second] = 0;
- std::vector<std::pair<long, long>> path;
- std::queue<std::pair<long, long>> toVisit;
- std::pair<long, long> currPos = startPos;
- toVisit.push(currPos);
- while(!toVisit.empty()) {
- currPos = toVisit.front();
- toVisit.pop();
- // if ((field[currPos.first][currPos.second] != INT_MAX) && (field[currPos.first][currPos.second] > field[path.back().first][path.back().second])) {
- // path.push_back(currPos);
- // }
- if (currPos == finishPos) {
- field[finishPos.first][finishPos.second] = field[path.back().first][path.back().second] + 1;
- break;
- }
- for (size_t i = currPos.first; i < n - 2; ++i) {
- for (size_t j = currPos.second; j < m - 2; ++j) {
- if ((i + deltas[0].first >= 0) && (j + deltas[0].second >= 0)) {
- if (field[i + deltas[0].first][j + deltas[0].second] == INT_MAX) {
- toVisit.push({i + deltas[0].first, j + deltas[0].second});
- field[i + deltas[0].first][j + deltas[0].second] = field[currPos.first][currPos.second] + 1;
- }
- }
- if ((i + deltas[1].first >= 0) && (j + deltas[1].second < m)) {
- if (field[i + deltas[1].first][j + deltas[1].second] == INT_MAX) {
- toVisit.push({i + deltas[1].first, j + deltas[1].second});
- field[i + deltas[1].first][j + deltas[1].second] = field[currPos.first][currPos.second] + 1;
- }
- }
- if ((i + deltas[2].first < n) && (j + deltas[2].second >= 0)) {
- if (field[i + deltas[2].first][j + deltas[2].second] == INT_MAX) {
- toVisit.push({i + deltas[2].first, j + deltas[2].second});
- field[i + deltas[2].first][j + deltas[2].second] = field[currPos.first][currPos.second] + 1;
- }
- }
- if ((i + deltas[3].first < n) && (j + deltas[3].second < m)) {
- if (field[i + deltas[3].first][j + deltas[3].second] == INT_MAX) {
- toVisit.push({i + deltas[3].first, j + deltas[3].second});
- field[i + deltas[3].first][j + deltas[3].second] = field[currPos.first][currPos.second] + 1;
- }
- }
- if ((i + deltas[4].first >= 0) && (j + deltas[4].second < m)) {
- if (field[i + deltas[4].first][j + deltas[4].second] == INT_MAX) {
- toVisit.push({i + deltas[4].first, j + deltas[4].second});
- field[i + deltas[4].first][j + deltas[4].second] = field[currPos.first][currPos.second] + 1;
- }
- }
- if ((i + deltas[5].first >= 0) && (j + deltas[5].second >= 0)) {
- if (field[i + deltas[5].first][j + deltas[5].second] == INT_MAX) {
- toVisit.push({i + deltas[5].first, j + deltas[5].second});
- field[i + deltas[5].first][j + deltas[5].second] = field[currPos.first][currPos.second] + 1;
- }
- }
- if ((i + deltas[6].first < n) && (j + deltas[6].second < m)) {
- if (field[i + deltas[6].first][j + deltas[6].second] == INT_MAX) {
- toVisit.push({i + deltas[6].first, j + deltas[6].second});
- field[i + deltas[6].first][j + deltas[6].second] = field[currPos.first][currPos.second] + 1;
- }
- }
- if ((i + deltas[7].first < n) && (j + deltas[7].second >= 0)) {
- if (field[i + deltas[7].first][j + deltas[7].second] == INT_MAX) {
- toVisit.push({i + deltas[7].first, j + deltas[7].second});
- field[i + deltas[7].first][j + deltas[7].second] = field[currPos.first][currPos.second] + 1;
- }
- }
- }
- }
- }
- if (std::find(path.begin(), path.end(), finishPos) == path.end()) {
- std::cout << -1 << std::endl;
- } else {
- std::cout << path.size() - 1 << std::endl;
- for (auto obj: path) {
- std::cout << obj.first << " " << obj.second << std::endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement