Advertisement
Guest User

Untitled

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