Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstdlib>
- #include <queue>
- using namespace std;
- #define x first
- #define y second
- const int dx[8] = {-2,-1,1,2,2,1,-1,-2};
- const int dy[8] = {1,2,2,1,-1,-2,-2,-1};
- const int INF = 1000000000;
- bool is_correct(int x,int y){
- return x >= 0 && x < 8 && y >= 0 && y < 8;
- }
- int main(){
- pair<int,int> start,finish;
- cin >> start.x >> start.y >> finish.x >> finish.y;
- queue<pair<int,int>> q;
- q.push({start.x - 1,start.y - 1});
- vector <vector<int>> dist(8,vector<int>(8,INF));
- dist[start.x - 1][start.y - 1] = 0;
- while (!q.empty()){
- auto p = q.front();
- q.pop();
- for (int i = 0; i < 8; i++){
- int x = p.x + dx[i];
- int y = p.y + dy[i];
- if (is_correct(x,y) && dist[x][y] > dist[p.x][p.y] + 1){
- dist[x][y] = dist[p.x][p.y] + 1;
- q.push({x,y});
- }
- }
- }
- int d = dist[finish.x - 1][finish.y - 1];
- if (d%2 == 0 && d != INF)
- {
- cout << d/2 << endl;
- }
- else{
- int min_dist = INF;
- for (int i = 0; i < 8; i++)
- {
- int x = finish.x + dx[i];
- int y = finish.y + dy[i];
- if (is_correct(x,y) && dist[x][y] % 2 == 0 && dist[x][y] < min_dist)
- min_dist = dist[x][y];
- }
- if (min_dist != INF)
- cout << min_dist/2 << endl;
- else
- cout << -1 << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement