Advertisement
Guest User

Untitled

a guest
Apr 20th, 2018
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <math.h>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. long long inf = 1000000000;
  9.  
  10. struct edge
  11. {
  12. long long a, b, cost;
  13. };
  14.  
  15. pair<long long,long long> solve(long long n, long long m, long long v, vector<edge>& e, vector<long long>& d, vector<long long>& c)
  16. {
  17. d[v] = 0;
  18. long long g = inf;
  19. long long fc = 0;
  20. for (long long i = 0; i < n*m - 1; i++)
  21. {
  22. for (long long j = 0; j < e.size(); j++)
  23. {
  24. if (d[e[j].a] < inf)
  25. {
  26. if (d[e[j].b] > d[e[j].a] + e[j].cost)
  27. {
  28. d[e[j].b] = d[e[j].a] + e[j].cost;
  29. }
  30. }
  31. long long l = max(c[e[j].b], d[e[j].b]);
  32. if(l < g)
  33. {
  34. g = l;
  35. fc = e[j].b;
  36. }
  37. l = max(c[e[j].a], d[e[j].a]);
  38. if(l < g)
  39. {
  40. g = l;
  41. fc = e[j].a;
  42. }
  43. }
  44. }
  45. return pair<long long,long long>(g,fc);
  46. }
  47.  
  48. void solve(long long n, long long m, long long v, vector<edge>& e, vector<long long>& d)
  49. {
  50. d[v] = 0;
  51. for (long long i = 0; i < n*m - 1; i++)
  52. {
  53. bool any = false;
  54. for (long long j = 0; j < e.size(); j++)
  55. {
  56. if (d[e[j].a] < inf)
  57. {
  58. if (d[e[j].b] > d[e[j].a] + e[j].cost)
  59. {
  60. d[e[j].b] = d[e[j].a] + e[j].cost;
  61. any = true;
  62. }
  63. }
  64. }
  65. if (!any)
  66. {
  67. break;
  68. }
  69. }
  70. }
  71.  
  72. int main()
  73. {
  74. long long n, m;
  75. cin >> n >> m;
  76. long long mas[301][301];
  77. vector<edge> ec;
  78. vector<edge> ed;
  79. vector<long long> c(n*m,inf);
  80. vector<long long> d(n*m,inf);
  81. for(long long i = 0; i < n; i++)
  82. {
  83. for(long long j = 0; j < m; j++)
  84. {
  85. cin >> mas[i][j];
  86. }
  87. }
  88. long long x1, y1, x2, y2;
  89. cin >> x1 >> y1 >> x2 >> y2;
  90. x1--;
  91. y1--;
  92. x2--;
  93. y2--;
  94. if(x1 == x2 && y1 == y2)
  95. {
  96. cout << "0\n" << x1 + 1 << " " << y1 + 1 << "\n";
  97. return 0;
  98. }
  99. long long v1 = x1*m + y1;
  100. long long v2 = x2*m + y2;
  101. for(long long i = 0; i < n; i++)
  102. {
  103. for(long long j = 0; j < m; j++)
  104. {
  105. int masx[4] = {1, -1, 0, 0};
  106. int masy[4] = {0, 0, 1, -1};
  107. for(int k = 0; k < 4; k++)
  108. {
  109. int ni = masx[k] + i;
  110. int nj = masy[k] + j;
  111. if(ni < 0 || ni >= n || nj < 0 || nj >= m)
  112. continue;
  113. if(mas[i][j] <= mas[ni][nj])
  114. {
  115. struct edge a;
  116. a.a = i*m+ j;
  117. a.b = (ni) * m + nj;
  118. a.cost = 1;
  119. ec.push_back(a);
  120. }
  121. if(mas[i][j] >= mas[ni][nj])
  122. {
  123. struct edge a;
  124. a.a = i*m + j;
  125. a.b = (ni) * m + nj;
  126. a.cost = 1;
  127. ed.push_back(a);
  128. }
  129. }
  130. }
  131. }
  132. solve(n, m, v1, ec,d);
  133. pair<int,int> an = solve(n, m, v2, ed,c,d);
  134. long long g = an.first;
  135. long long fc = an.second / m;
  136. long long fd = an.second % m;
  137. if(g == inf)
  138. {
  139. cout << -1 << "\n";
  140. return 0;
  141. }
  142. else
  143. {
  144. cout << g << "\n" << fc + 1 << " " << fd + 1 << "\n";
  145. }
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement