Advertisement
Guest User

Untitled

a guest
Aug 26th, 2016
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.49 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdlib>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. #define x first
  9. #define y second
  10.  
  11. const int dx[8] = {-2,-1,1,2,2,1,-1,-2};
  12. const int dy[8] = {1,2,2,1,-1,-2,-2,-1};
  13.  
  14. const int INF = 1000000000;
  15.  
  16. bool is_correct(int x,int y){
  17. return x >= 0 && x < 8 && y >= 0 && y < 8;
  18. }
  19.  
  20. int main(){
  21. pair<int,int> start,finish;
  22. cin >> start.x >> start.y >> finish.x >> finish.y;
  23. queue<pair<int,int>> q;
  24. q.push({start.x - 1,start.y - 1});
  25. vector <vector<int>> dist(8,vector<int>(8,INF));
  26. dist[start.x - 1][start.y - 1] = 0;
  27.  
  28. while (!q.empty()){
  29. auto p = q.front();
  30. q.pop();
  31. for (int i = 0; i < 8; i++){
  32. int x = p.x + dx[i];
  33. int y = p.y + dy[i];
  34. if (is_correct(x,y) && dist[x][y] > dist[p.x][p.y] + 1){
  35. dist[x][y] = dist[p.x][p.y] + 1;
  36. q.push({x,y});
  37. }
  38. }
  39. }
  40.  
  41. int d = dist[finish.x - 1][finish.y - 1];
  42. if (d%2 == 0 && d != INF)
  43. {
  44. cout << d/2 << endl;
  45. }
  46. else{
  47. int min_dist = INF;
  48. for (int i = 0; i < 8; i++)
  49. {
  50. int x = finish.x + dx[i];
  51. int y = finish.y + dy[i];
  52. if (is_correct(x,y) && dist[x][y] % 2 == 0 && dist[x][y] < min_dist)
  53. min_dist = dist[x][y];
  54. }
  55. if (min_dist != INF)
  56. cout << min_dist/2 << endl;
  57. else
  58. cout << -1 << endl;
  59. }
  60.  
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement