Advertisement
mickypinata

TOCPC2021: Long Jump

Nov 24th, 2021
808
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define r first
  5. #define c second
  6. typedef pair<int, int> pii;
  7. typedef pair<pii, int> ppi;
  8.  
  9. const int N = 1e6 + 5;
  10. const pii dir[4] = {pii(-1, 0), pii(1, 0), pii(0, -1), pii(0, 1)}; // U D L R
  11.  
  12. enum direction {
  13.     UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3
  14. };
  15.  
  16. map<pii, int> ed;
  17. set<pii> visited;
  18. vector<int> adj[2][N];
  19.  
  20. pii moveToWall(pii st, int d){
  21.     pii ans = pii(0, 0);
  22.     if(d == UP){
  23.         ans.c = st.c;
  24.         ans.r = *(lower_bound(adj[1][st.c].begin(), adj[1][st.c].end(), st.r) - 1);
  25.     } else if(d == DOWN){
  26.         ans.c = st.c;
  27.         ans.r = *upper_bound(adj[1][st.c].begin(), adj[1][st.c].end(), st.r);
  28.     } else if(d == LEFT){
  29.         ans.r = st.r;
  30.         ans.c = *(lower_bound(adj[0][st.r].begin(), adj[0][st.r].end(), st.c) - 1);
  31.     } else if(d == RIGHT){
  32.         ans.r = st.r;
  33.         ans.c = *upper_bound(adj[0][st.r].begin(), adj[0][st.r].end(), st.c);
  34.     }
  35.     return pii(ans.r - dir[d].r, ans.c - dir[d].c);
  36. }
  37.  
  38. int main(){
  39.  
  40.     int row, col, nWall;
  41.     pii st, ed;
  42.     scanf("%d%d%d%d%d%d%d", &row, &col, &nWall, &st.r, &st.c, &ed.r, &ed.c);
  43.     for(int i = 1; i <= nWall; ++i){
  44.         int r, c;
  45.         scanf("%d%d", &r, &c);
  46.         adj[0][r].push_back(c);
  47.         adj[1][c].push_back(r);
  48.     }
  49.     for(int i = 1; i <= row; ++i){
  50.         if(!adj[0][i].empty()){
  51.             adj[0][i].push_back(0);
  52.             sort(adj[0][i].begin(), adj[0][i].end());
  53.             adj[0][i].push_back(col + 1);
  54.         } else {
  55.             adj[0][i].push_back(0);
  56.             adj[0][i].push_back(col + 1);
  57.         }
  58.     }
  59.     for(int j = 1; j <= col; ++j){
  60.         if(!adj[1][j].empty()){
  61.             adj[1][j].push_back(0);
  62.             sort(adj[1][j].begin(), adj[1][j].end());
  63.             adj[1][j].push_back(row + 1);
  64.         } else {
  65.             adj[1][j].push_back(0);
  66.             adj[1][j].push_back(row + 1);
  67.         }
  68.     }
  69.     queue<ppi> que;
  70.     visited.insert(ed);
  71.     que.emplace(ed, 0);
  72.     while(!que.empty()){
  73.         pii u = que.front().r;
  74.         int dist = que.front().c;
  75.         que.pop();
  76.         if(u == st){
  77.             cout << dist;
  78.             return 0;
  79.         }
  80.         for(int d = 0; d < 4; ++d){
  81.             pii v = moveToWall(u, d);
  82.             if(visited.find(v) == visited.end()){
  83.                 visited.insert(v);
  84.                 que.emplace(v, dist + 1);
  85.             }
  86.         }
  87.     }
  88.     cout << "-1";
  89.  
  90.     return 0;
  91. }
  92.  
Advertisement
RAW Paste Data Copied
Advertisement