Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- #include <string>
- #include <deque>
- using namespace std;
- int main()
- {
- ifstream IN;
- ofstream OUT;
- IN.open("in.txt");
- string str = "";
- string buffer = "";
- int count_of_rows = 0, count_of_cols = 0;
- getline(IN, str);
- str += ' ';
- for (int i = 0; i < str.size(); i++)
- {
- if (str[i] != ' ')
- buffer += str[i];
- if (str[i] == ' ')
- {
- bool check = false;
- if ((count_of_rows == 0) && (check == false))
- count_of_rows = stoi(buffer);
- else if ((count_of_cols == 0) && (check == false))
- count_of_cols = stoi(buffer);
- buffer = "";
- }
- }
- buffer = "";
- vector<vector<int>> matrix(count_of_rows, vector<int>(count_of_cols));
- for (int i = 0; i < count_of_rows; i++)
- {
- int counter = 0;
- getline(IN, str);
- str += " ";
- for (int j = 0; j < str.size(); j++)
- {
- if (str[j] != ' ')
- {
- buffer += str[j];
- }
- if (str[j] == ' ')
- {
- int elem = stoi(buffer);
- matrix[i][counter] = elem;
- counter++;
- buffer = "";
- }
- }
- }
- buffer = "";
- int x_s = 0, y_s = 0, x_e = 0, y_e = 0;
- getline(IN, str);
- str += " ";
- for (int i = 0; i < str.size(); i++)
- {
- bool check = false;
- if (str[i] != ' ')
- buffer += str[i];
- if (str[i] == ' ')
- {
- if((x_s == 0) && (check == false))
- x_s = stoi(buffer);
- else if(y_s == 0 && check == false)
- y_s = stoi(buffer);
- else if(x_e == 0 && check == false)
- x_e = stoi(buffer);
- else if(y_e == 0 && check == false)
- y_e = stoi(buffer);
- buffer = "";
- }
- }
- IN.close();
- vector< pair<int,int>> steps = { {-2, -1}, {-2, 1}, {2, 1}, {2, -1}, {1, 2}, {-1, 2},{1, -2}, {-1, -2} };
- deque<pair<int, int>> q;
- matrix[(long)x_s - 1][(long)y_s - 1] = 1;
- q.push_back(make_pair(x_s - 1, y_s - 1));
- int result = -1;
- bool check = false;
- int j = 0;
- while (true)
- {
- for (int i = 0; i < steps.size(); i++)
- {
- if ((0 <= q[j].first + steps[i].first) && (q[j].first + steps[i].first < count_of_rows))
- {
- if ((0 <= q[j].second + steps[i].second) && (q[j].second + steps[i].second < count_of_cols))
- {
- int cur_x = (q[j].first) + (steps[i].first);
- int cur_y = (q[j].second) + (steps[i].second);
- if (matrix[cur_x][cur_y] == 0)
- {
- q.push_back(make_pair(cur_x, cur_y));
- matrix[cur_x][cur_y] = matrix[q[j].first][q[j].second] + 1;
- if (cur_x == x_e - 1 && cur_y == y_e - 1)
- {
- result = matrix[cur_x][cur_y] - 1;
- check = true;
- break;
- }
- }
- }
- }
- }
- q.pop_front();
- if (check == true || q.empty())
- {
- break;
- }
- }
- OUT.open("out.txt");
- if (x_s == x_e && y_s == y_e)
- {
- result = 0;
- }
- if (result == -1)
- {
- OUT << "No";
- }
- else
- {
- OUT << result;
- }
- OUT.close();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement