Advertisement
Guest User

Untitled

a guest
Dec 16th, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.88 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6. vector<vector<int>> g;
  7. queue<pair<int, int>> Q;
  8. int di[8] = { -1,-2,-2,-1,1,2,2,1 };
  9. int dj[8] = { -2,-1,1,2,2,1,-1,-2 };
  10.  
  11. void bfs()
  12. {
  13. while (!Q.empty())
  14. {
  15. pair<int, int> cur = Q.front(); Q.pop();
  16. for (int i = 0; i < 8; i++)
  17. {
  18. int ni = cur.first + di[i]; int nj = cur.second + dj[i];
  19. if (ni > 0 && ni <= 8 && nj > 0 && nj <= 8)
  20. {
  21. if (g[ni][nj] > g[cur.first][cur.second] + 1)
  22. {
  23. Q.push({ ni,nj });
  24. g[ni][nj] = g[cur.first][cur.second] + 1;
  25. }
  26. }
  27. }
  28. }
  29. }
  30. int main()
  31. {
  32. char a, b, c, d;
  33. cin >> a >> b >> c >> d;
  34. g.resize(9, vector<int>(9, 999999));
  35. int x1 = a - 'a' + 1, x2 = c - 'a' + 1, y1 = b - '0', y2 = d - '0';
  36. Q.push({ x1, y1 });
  37. g[x1][y1] = 0;
  38. bfs();
  39. if (!(g[x2][y2] & 1)) cout << g[x2][y2] / 2;
  40. else cout << -1;
  41. return 0;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement