Advertisement
Guest User

Untitled

a guest
Nov 8th, 2020
531
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define endl "\n"
  3.  
  4. using namespace std;
  5. main() {
  6. ios_base::sync_with_stdio(0);
  7. cin.tie(0);
  8. int n, m, k, q;
  9. cin >> n >> m >> k >> q;
  10. vector<vector<int> > pref(n, vector<int> (m));
  11. vector<pair<int, int>> blm(k);
  12. for(int b = 0; b < k; b++) {
  13. int i, j;
  14. cin >> i >> j;
  15. i--;j--;
  16. pref[i][j] = 1;
  17. blm[b] = {i, j};
  18. }
  19. for(int i = 0; i < n; i++) {
  20. for(int j = 0; j < m; j++) {
  21. if(i > 0) pref[i][j] += pref[i - 1][j];
  22. if(j > 0) pref[i][j] += pref[i][j - 1];
  23. if(i > 0 && j > 0) {
  24. pref[i][j] -= pref[i - 1][j - 1];
  25. }
  26. }
  27. }
  28. auto rect = [&](int li, int lj, int hi, int hj) {
  29. int res = pref[hi][hj];
  30. if(lj > 0) {
  31. res -= pref[hi][lj - 1];
  32. }
  33. if(li > 0) {
  34. res -= pref[li - 1][hj];
  35. }
  36. if(li > 0 && lj > 0) {
  37. res += pref[li - 1][lj - 1];
  38. }
  39. return res;
  40. };
  41. // preprocess
  42. const int inf = 1e7;
  43. vector<vector<vector<vector<int>>>> dist(4, vector<vector<vector<int>>> (k, vector<vector<int>> (n, vector<int> (m, inf))));
  44. const int di[4] = {-1, 1, 0, 0};
  45. const int dj[4] = {0, 0, -1, 1};
  46. vector<pair<int, int>> qr;
  47. auto get = [&](int si, int sj, vector<vector<int>> &dis) {
  48. qr = vector<pair<int, int>> ();
  49. dis[si][sj] = 0;
  50. qr.push_back({si, sj});
  51. for(int v = 0; v < qr.size(); v++) {
  52. int i = qr[v].first, j = qr[v].second;
  53. for(int dir = 0; dir < 4; dir++) {
  54. int ni = i + di[dir];
  55. int nj = j + dj[dir];
  56. if(ni >= 0 && ni < n && nj >= 0 && nj < m && dis[ni][nj] == inf && rect(ni, nj, ni, nj) != 1) {
  57. dis[ni][nj] = dis[i][j] + 1;
  58. qr.push_back({ni, nj});
  59. }
  60. }
  61. }
  62. };
  63. for(int b = 0; b < k; b++) {
  64. int i = blm[b].first;
  65. int j = blm[b].second;
  66. for(int dir = 0; dir < 4; dir++) {
  67. int ni = i + di[dir];
  68. int nj = j + dj[dir];
  69. if(ni >= 0 && ni < n && nj >= 0 && nj < m && rect(ni, nj, ni, nj) != 1) get(ni, nj, dist[dir][b]);
  70. }
  71. }
  72. while(q--) {
  73. int si, sj, ei, ej;
  74. cin >> si >> sj >> ei >> ej;
  75. si--;
  76. sj--;
  77. ei--;
  78. ej--;
  79. if(rect(si, sj, si, sj) || rect(ei, ej, ei, ej)) {
  80. cout << -1 << endl;
  81. continue;
  82. }
  83. if(rect(min(si, ei), min(sj, ej), max(si, ei), max(sj, ej)) == 0) {
  84. cout << abs(si - ei) + abs(sj - ej) << endl;
  85. continue;
  86. }
  87. int ans = inf;
  88. for(int b = 0; b < k; b++) {
  89. int i = blm[b].first;
  90. int j = blm[b].second;
  91. for(int dir = 0; dir < 4; dir++) {
  92. int ni = i + di[dir];
  93. int nj = j + dj[dir];
  94. if(ni >= 0 && ni < n && nj >= 0 && nj < m && rect(ni, nj, ni, nj) != 1) {
  95. ans = min(ans, dist[dir][b][si][sj] + dist[dir][b][ei][ej]);
  96. }
  97. }
  98. }
  99. if(ans >= inf) {
  100. cout << -1 << endl;
  101. } else {
  102. cout << ans << endl;
  103. }
  104. }
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement