Guest User

Untitled

a guest
Jun 21st, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.48 KB | None | 0 0
  1. /*
  2. Factor común
  3. */
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <iterator>
  7. #include <iomanip>
  8. #include <sstream>
  9. #include <fstream>
  10. #include <cassert>
  11. #include <climits>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <string>
  15. #include <cstdio>
  16. #include <vector>
  17. #include <cmath>
  18. #include <queue>
  19. #include <deque>
  20. #include <stack>
  21. #include <list>
  22. #include <map>
  23. #include <set>
  24. using namespace std;
  25.  
  26. template <class T> string toStr(const T &x){ stringstream s; s << x; return s.str(); }
  27. template <class T> int toInt(const T &x){ stringstream s; s << x; int r; s >> r; return r; }
  28.  
  29. #define For(i, a, b) for (int i=(a); i<(b); ++i)
  30. #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  31. #define D(x) cout << #x " = " << (x) << endl;
  32.  
  33. const double EPS = 1e-9;
  34. int cmp(double x, double y = 0, double tol = EPS){
  35. return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  36. }
  37.  
  38. //#define LECTURA_ARCHIVO
  39. #define ARCHIVO ""
  40.  
  41. const int MAXN = 1005;
  42.  
  43. int score[MAXN][MAXN];
  44. int X, Y;
  45. int d[MAXN][MAXN];
  46. pair<int, int> start, end;
  47.  
  48. int dx[] = {-1, +1, +0, +0};
  49. int dy[] = {+0, +0, -1, +1};
  50.  
  51. bool inside(int x, int y){
  52. return 0 <= x && x < X && 0 <= y && y < Y;
  53. }
  54.  
  55. bool llega(int cota){
  56. //printf("llega con %d?\n", cota);
  57. memset(d, -1, sizeof d);
  58. queue<pair<int, int> > q;
  59. q.push(start);
  60. d[start.first][start.second] = 0;
  61. if (score[start.first][start.second] < cota) return false;
  62. while (q.size()){
  63. int x = q.front().first, y = q.front().second;
  64. q.pop();
  65. //printf("popped (%d, %d), score = %d\n", x, y, score[x][y]);
  66. if (make_pair(x, y) == end) return true;
  67. for (int k=0; k<4; ++k){
  68. int nx = x + dx[k];
  69. int ny = y + dy[k];
  70. if (!inside(nx, ny)) continue;
  71. if (d[nx][ny] != -1) continue;
  72. if (score[nx][ny] < cota) continue;
  73. d[nx][ny] = d[x][y] + 1;
  74. q.push(make_pair(nx, ny));
  75. }
  76. }
  77. return false;
  78. }
  79.  
  80.  
  81. int main() {
  82. #ifdef LECTURA_ARCHIVO
  83. freopen(ARCHIVO ".in", "r", stdin);
  84. #endif
  85.  
  86. int Casos;
  87. cin >> Casos;
  88. while (Casos--){
  89. int bases;
  90. cin >> bases >> X >> Y;
  91. cin >> start.first >> start.second >> end.first >> end.second;
  92.  
  93. memset(score, -1, sizeof score);
  94. queue<pair<int, int> > q;
  95. for (int i=0; i<bases; ++i){
  96. int x, y;
  97. cin >> x >> y;
  98. q.push(make_pair(x, y));
  99. score[x][y] = 0;
  100. }
  101.  
  102. //fill score
  103. while (q.size()){
  104. int x = q.front().first, y = q.front().second;
  105. q.pop();
  106. for (int k=0; k<4; ++k){
  107. int nx = x + dx[k];
  108. int ny = y + dy[k];
  109. if (!inside(nx, ny)) continue;
  110. if (score[nx][ny] != -1) continue;
  111. score[nx][ny] = score[x][y] + 1;
  112. q.push(make_pair(nx, ny));
  113. }
  114. }
  115.  
  116. //For(i, 0, X){ For(j, 0, Y) printf("%2d ", score[i][j]); puts(""); }
  117.  
  118. //llene la matriz, binary search
  119. int low = 0, high = 3*(X + Y);
  120. while (low < high){
  121. int mid = (low + high + 1) / 2;
  122. if (llega(mid)) low = mid;
  123. else high = mid - 1;
  124. }
  125. assert(low == high);
  126. assert(llega(low));
  127. printf("%d %d\n", low, d[end.first][end.second]);
  128. }
  129.  
  130. return 0;
  131. }
Add Comment
Please, Sign In to add comment