#ifndef INCLUDED_MAIN #define INCLUDED_MAIN #include __FILE__ int main(void){ int h, w; cin >> h >> w; int a, b; cin >> a >> b; a--;b--; int o,p,q,r; cin >> o >> p >> q >> r; o--;p--;q--;r--; int s,t; cin >> s >> t; s--;t--; array>,2> v; v[0].resize(h,vector(w,-1)); v[1].resize(h,vector(w,-1)); queue> u; u.push({0,a,b}); while(!u.empty()){ auto [d,x,y] = u.front(); u.pop(); if(d==1 && x==s && y==t){ break; } array dxy = {0,1,0,-1,0}; int i; rep(i,4){ int nx = x + dxy[i]; int ny = y + dxy[i+1]; if(nx<0 || h<=nx || ny<0 || w<=ny){ continue; } if(o<=nx && nx <= q && p <= ny && ny<=r){ if(v[1][nx][ny] == -1){ u.push({1,nx,ny}); v[1][nx][ny] = v[d][x][y]+1; } }else{ if(v[d][nx][ny] == -1){ u.push({d,nx,ny}); v[d][nx][ny] = v[d][x][y]+1; } } } } cout << v[1][s][t] + abs(a-s) + abs(t-b) + 1 << "\n"; } #else #include using namespace std; using ll = long long; using ld= long double; #define rep(i,n) for(i=0;i<(n);i++) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() namespace nskr{ template struct sortedset{ struct node{ T key; int level; node *left, *right; int lcount, rcount; node(T x) :key(x), level(0), left(nullptr), right(nullptr),lcount(0),rcount(0){} }; node* sentinel; private: node* root; node* skew(node* x){ //左同levelを解決 if(x==nullptr) return nullptr; if(x->left==nullptr) return x; if(x->left->level==x->level){ node* leftnode = x->left; x->left = leftnode->right; leftnode->right = x; // swap(leftnode->rcount, x->lcount); // leftnode->lcount += x->rcount - leftnode->lcount; setcount(x); setcount(leftnode); return leftnode; }else{ return x; } } node* split(node* x){ //右連続同levelを解決 if(x==nullptr) return nullptr; if(x->right==nullptr) return x; if(x->right->right==nullptr) return x; if(x->right->right->level == x->level){ node* rightnode = x->right; x->right = rightnode->left; rightnode->left = x; rightnode->level++; // swap(x->rcount,rightnode->lcount); // rightnode->lcount += x->lcount - rightnode->rcount; setcount(x); setcount(rightnode); return rightnode; }else{ return x; } } void setcount(node* x){ if(x==nullptr) return; if(x->left == nullptr) x->lcount = 0; else x->lcount = x->left->lcount + x->left->rcount + 1; if(x->right == nullptr) x->rcount = 0; else x->rcount = x->right->lcount + x->right->rcount + 1; x->rcount+=0; return; } node* insert(node* x, T key){ if(x == nullptr) return new node(key); if(x->key < key){ x->right = insert(x->right, key); }else if(x->key > key){ x->left = insert(x->left , key); } else return x; setcount(x); return split(skew(x)); } node* erase(node* x, T key){ if(x == nullptr) return nullptr; if(key < x->key) { x-> left = erase(x->left, key); }else if(key > x->key) x->right=erase(x->right, key); else{ if(x->left == nullptr){ node* ret = x->right; delete x; return ret; } if(x->right == nullptr){ node* ret = x->left; delete x; return ret; } node* tgt = x->right; while(tgt->left != nullptr) tgt = tgt->left; x->key = tgt->key; x->right = erase(x->right, tgt->key); } setcount(x); int newlevel = min( (x->left == nullptr ? 0 : x->left->level), (x->right == nullptr ? 0 : x->right->level) )+1; if(newlevel < x->level){ x->level = newlevel; if(x->right != nullptr && newlevel < x->right->level){ x->right->level = newlevel; } } x = skew(x); if(x->right != nullptr){ x->right = skew(x->right); if(x->right->right != nullptr) x->right->right = skew(x->right->right); } x = split(x); if(x->right != nullptr) x->right = split(x->right); return x; } node* get(node* x, int t){ if(x==nullptr) return nullptr; if(x->lcount < t) return get(x->right, t-x->lcount-1); if(x->lcount > t) return get(x->left, t); return x; } node* lower_bound(node* x, T key){//key以上の最小 if(x == nullptr)return sentinel; if(x->key < key){ return lower_bound(x->right, key); }if(x->key > key){ node* ret = lower_bound(x->left, key); if(ret == sentinel) return x; else return ret; } return x; } node* upper_bound(node* x, T key){//key以下の最大 if(x == nullptr)return sentinel; if(x->key > key){ return upper_bound(x->left, key); }if(x->key < key){ node* ret = upper_bound(x->right, key); if(ret == sentinel) return x; else return ret; } return x; } int rank(node* x, T key){ if(x==nullptr) return 0; if(x->key==key) return x->lcount+1; if(x->keyright,key) + x->lcount+1; } if(x->key>key){ return rank(x->left,key); } } public: sortedset():root(nullptr),sentinel(0){} const T operator[](int t){ node* x = get(root, t); if(x==nullptr) return T(); else return x->key; } size_t size(){ if(root==nullptr)return 0; return root->lcount + root->rcount + 1; } void insert(T key){root = insert(root, key);} void erase(T key){root = erase(root, key);} node* lower_bound(T key){return lower_bound(root,key);} node* upper_bound(T key){return upper_bound(root,key);} int rank(T key){return rank(root,key);} }; } #endif