Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define endl "\n"
- using namespace std;
- main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int n, m, k, q;
- cin >> n >> m >> k >> q;
- vector<vector<int> > pref(n, vector<int> (m));
- vector<pair<int, int>> blm(k);
- for(int b = 0; b < k; b++) {
- int i, j;
- cin >> i >> j;
- i--;j--;
- pref[i][j] = 1;
- blm[b] = {i, j};
- }
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- if(i > 0) pref[i][j] += pref[i - 1][j];
- if(j > 0) pref[i][j] += pref[i][j - 1];
- if(i > 0 && j > 0) {
- pref[i][j] -= pref[i - 1][j - 1];
- }
- }
- }
- auto rect = [&](int li, int lj, int hi, int hj) {
- int res = pref[hi][hj];
- if(lj > 0) {
- res -= pref[hi][lj - 1];
- }
- if(li > 0) {
- res -= pref[li - 1][hj];
- }
- if(li > 0 && lj > 0) {
- res += pref[li - 1][lj - 1];
- }
- return res;
- };
- // preprocess
- const int inf = 1e7;
- vector<vector<vector<vector<int>>>> dist(4, vector<vector<vector<int>>> (k, vector<vector<int>> (n, vector<int> (m, inf))));
- const int di[4] = {-1, 1, 0, 0};
- const int dj[4] = {0, 0, -1, 1};
- vector<pair<int, int>> qr;
- auto get = [&](int si, int sj, vector<vector<int>> &dis) {
- qr = vector<pair<int, int>> ();
- dis[si][sj] = 0;
- qr.push_back({si, sj});
- for(int v = 0; v < qr.size(); v++) {
- int i = qr[v].first, j = qr[v].second;
- for(int dir = 0; dir < 4; dir++) {
- int ni = i + di[dir];
- int nj = j + dj[dir];
- if(ni >= 0 && ni < n && nj >= 0 && nj < m && dis[ni][nj] == inf && rect(ni, nj, ni, nj) != 1) {
- dis[ni][nj] = dis[i][j] + 1;
- qr.push_back({ni, nj});
- }
- }
- }
- };
- for(int b = 0; b < k; b++) {
- int i = blm[b].first;
- int j = blm[b].second;
- for(int dir = 0; dir < 4; dir++) {
- int ni = i + di[dir];
- int nj = j + dj[dir];
- if(ni >= 0 && ni < n && nj >= 0 && nj < m && rect(ni, nj, ni, nj) != 1) get(ni, nj, dist[dir][b]);
- }
- }
- while(q--) {
- int si, sj, ei, ej;
- cin >> si >> sj >> ei >> ej;
- si--;
- sj--;
- ei--;
- ej--;
- if(rect(si, sj, si, sj) || rect(ei, ej, ei, ej)) {
- cout << -1 << endl;
- continue;
- }
- if(rect(min(si, ei), min(sj, ej), max(si, ei), max(sj, ej)) == 0) {
- cout << abs(si - ei) + abs(sj - ej) << endl;
- continue;
- }
- int ans = inf;
- for(int b = 0; b < k; b++) {
- int i = blm[b].first;
- int j = blm[b].second;
- for(int dir = 0; dir < 4; dir++) {
- int ni = i + di[dir];
- int nj = j + dj[dir];
- if(ni >= 0 && ni < n && nj >= 0 && nj < m && rect(ni, nj, ni, nj) != 1) {
- ans = min(ans, dist[dir][b][si][sj] + dist[dir][b][ei][ej]);
- }
- }
- }
- if(ans >= inf) {
- cout << -1 << endl;
- } else {
- cout << ans << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement