Advertisement
Guest User

Untitled

a guest
Apr 19th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.59 KB | None | 0 0
  1. #include<algorithm>
  2. #include<iostream>
  3. #include<vector>
  4. #include<queue>
  5.  
  6.  
  7. using namespace std;
  8.  
  9. int h, l;
  10. vector<vector<int>> jumps = {{2,1}, {2,-1}, {-2,1}, {-2,-1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
  11.  
  12.  
  13. bool is_exist_way(int x, int y) {
  14. return (x >= 0 && y >= 0 && y <= h && x <= l);
  15. }
  16.  
  17.  
  18. vector<int> d;
  19.  
  20. void bfs(int source, int n, vector<vector<int>> &g) {
  21. d.resize(h * l);
  22. fill(d.begin(), d.end(), -1);
  23. queue<int> q;
  24. q.push(source);
  25. d[source] = 0;
  26. while (!q.empty()) {
  27. int v = q.front();
  28. q.pop();
  29. for (int i = 0; i != g[v].size(); ++i) {
  30. if (d[i] == -1) {
  31. d[i] = d[v] + 1;
  32. q.push(i);
  33. }
  34. }
  35. }
  36. }
  37.  
  38. int main() {
  39. cin >> l >> h;
  40. int s, t;
  41. cin >> s >> t;
  42. int trap = s * l + t;
  43. int n;
  44. cin >> n;
  45. vector<int> fleas(n);
  46. for (int i = 0; i != n; ++i) {
  47. int x, y;
  48. cin >> x >> y;
  49. fleas[i] = x * l + y;
  50. }
  51. vector<vector<int>> g(h * l);
  52. for (int i = 0; i != l; ++i) {
  53. for (int j = 0; j != h; ++j) {
  54. for (int k = 0; k <= 7; ++k) {
  55. int x = i + jumps[k][0];
  56. int y = j + jumps[k][1];
  57. if (is_exist_way(x, y)) {
  58. g[i*l + j].emplace_back(x*l + y);
  59. }
  60. }
  61. }
  62. }
  63. bfs(trap, g.size(), g);
  64. int sum = -1;
  65. for (int i = 0; i != n; ++i) {
  66. sum += d[fleas[i]];
  67. }
  68. if (sum == -1) {
  69. cout << "-1";
  70. } else {
  71. cout << sum + 1;
  72. }
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement