#pragma region includes #ifdef LOCAL #define _GLIBCXX_DEBUG #endif #include #include #include #include using namespace __gnu_pbds; using namespace std; using namespace atcoder; using ll = long long; using ull = unsigned long long; struct custom_hash { static ull splitmix64(ull x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } static ull hash_any(ull x) { static const ull FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } size_t operator()(ull x) const { return hash_any(x); } size_t operator()(const string& s) const { return hash_any(std::hash{}(s)); } template size_t operator()(const pair& p) const { ull h1 = (*this)(p.first); ull h2 = (*this)(p.second); return splitmix64(h1 ^ (h2 + 0x9e3779b97f4a7c15 + (h1 << 6) + (h1 >> 2))); } }; template struct safe_map : gp_hash_table { bool count(const K& k) const { return this->find(k) != this->end(); } }; template struct safe_set : gp_hash_table { bool count(const K& k) const { return this->find(k) != this->end(); } }; template using umap = unordered_map; template using uset = unordered_set; // --- PBDS --- // 直感的に使える ordered_set (重複を許さない単一要素版) のラッパー template struct OrderedSet { tree, rb_tree_tag, tree_order_statistics_node_update> st; // 要素 x を追加 (既に存在する場合は何もしない) void insert(T x) { st.insert(x); } // 要素 x を削除 (存在する場合のみ) void erase(T x) { st.erase(x); } // 小さい方から k 番目 (0-indexed) の値を取得 T get_kth(int k) { return *st.find_by_order(k); } // x より小さい要素の個数を取得 int count_less(T x) { return st.order_of_key(x); } // 要素 x が存在するかどうかを判定 bool contains(T x) { return st.find(x) != st.end(); } int size() { return st.size(); } bool empty() { return st.empty(); } void clear() { st.clear(); } }; // 直感的に使える ordered_multiset のラッパー template struct OrderedMultiset { int id_counter = 0; tree, null_type, less>, rb_tree_tag, tree_order_statistics_node_update> st; // 要素 x を追加 void insert(T x) { st.insert({x, id_counter++}); } // 要素 x を 1 つ削除 (存在する場合のみ) void erase(T x) { auto it = st.lower_bound({x, -1}); if (it != st.end() && it->first == x) st.erase(it); } // 小さい方から k 番目 (0-indexed) の値を取得 T get_kth(int k) { return st.find_by_order(k)->first; } // x より小さい要素の個数を取得 int count_less(T x) { return st.order_of_key({x, -1}); } // x 以下の要素の個数を取得 int count_less_equal(T x) { return st.order_of_key({x, 2000000000}); // IDとして十分に大きな値を使用 } int size() { return st.size(); } bool empty() { return st.empty(); } void clear() { st.clear(); id_counter = 0; } }; // ----------- constexpr int MOD = 1000000007; constexpr int MOD998 = 998244353; using mint = atcoder::static_modint; using mint998 = atcoder::static_modint; using dmint = atcoder::modint; inline void set_mod(long long p) { dmint::set_mod(p); } using int128 = __int128_t; using uint128 = __uint128_t; constexpr uint128 INT128_ABS_MIN = uint128{1} << 127; constexpr int128 INT128_MAX_VALUE = static_cast(INT128_ABS_MIN - 1); constexpr int128 INT128_MIN_VALUE = -INT128_MAX_VALUE - 1; std::istream& operator>>(std::istream& is, __int128_t& v) { std::string s; if (!(is >> s)) return is; size_t pos = 0; bool negative = false; if (s[pos] == '+' || s[pos] == '-') { negative = (s[pos] == '-'); pos++; } if (pos == s.size()) { is.setstate(std::ios::failbit); return is; } const uint128 limit = negative ? INT128_ABS_MIN : static_cast(INT128_MAX_VALUE); uint128 value = 0; for (; pos < s.size(); pos++) { const char c = s[pos]; if (c < '0' || c > '9') { is.setstate(std::ios::failbit); return is; } const uint128 digit = static_cast(c - '0'); if (value > (limit - digit) / 10) { is.setstate(std::ios::failbit); return is; } value = value * 10 + digit; } if (negative) { v = (value == INT128_ABS_MIN) ? INT128_MIN_VALUE : -static_cast(value); } else { v = static_cast(value); } return is; } std::ostream& operator<<(std::ostream& os, __int128_t v) { if (v == 0) return os << '0'; uint128 value; if (v < 0) { os << '-'; value = static_cast(-(v + 1)) + 1; } else { value = static_cast(v); } char digits[40]; int len = 0; while (value > 0) { digits[len++] = static_cast('0' + value % 10); value /= 10; } while (len > 0) os << digits[--len]; return os; } template istream& operator>>(istream& is, atcoder::static_modint& v) { long long x; is >> x; v = x; return is; } template ostream& operator<<(ostream& os, const atcoder::static_modint& v) { return os << v.val(); } template istream& operator>>(istream& is, atcoder::dynamic_modint& v) { long long x; is >> x; v = x; return is; } template ostream& operator<<(ostream& os, const atcoder::dynamic_modint& v) { return os << v.val(); } #define rep(i, x, limit) for (ll i = (ll)x; i < (ll)limit; i++) #define rrep(i, x, limit) for (ll i = (ll)x; i >= (ll)limit; i--) #define reps(i, a, b, s) for (long long i = (a); i < (b); i += (s)) #define rreps(i, a, b, s) for (long long i = (a); i >= (b); i -= (s)) #define rep2(i, start_i, limit_i, j, start_j, limit_j) for (ll i = (ll)(start_i); i < (ll)(limit_i); i++) for (ll j = (ll)(start_j); j < (ll)(limit_j); j++) constexpr int inf = 1073741823; constexpr ll infl = 1LL << 60; // 右、下、左、上の順 constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; // 右、右下、下、左下、左、左上、上、右上の順 constexpr int dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1}; const long double PI = 3.1415926535897932384626433832795028841971; constexpr array make_p10() { array p{}; p[0] = 1; for (int i = 1; i < (int)p.size(); i++) p[i] = p[i - 1] * 10; return p; } constexpr auto P10 = make_p10(); inline constexpr long long pow2(int i) { return 1LL << i; } inline int bitcount(long long x) { return __builtin_popcountll(x); } #define alp "abcdefghijklmnopqrstuvwxyz" #define ALP "ABCDEFGHIJKLMNOPQRSTUVWXYZ" #define nall(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define pb push_back #define pob pop_back #define eb emplace_back #define Yes cout << "Yes" << endl #define No cout << "No" << endl #define YES cout << "YES" << endl #define NO cout << "NO" << endl void YN(bool cond) { cout << (cond ? "Yes" : "No") << "\n"; } #define endl "\n" #define syousu cout< istream& operator>>(istream& is, pair& p) { is >> p.first >> p.second; return is; } template istream& operator>>(istream& is, vector& v) { for (auto& e : v) is >> e; return is; } // 出力ヘルパー(複数の値は空白区切り、末尾は改行) inline void p0() { cout << '\n'; } template void print_line(const Args&... args) { size_t i = 0; ((cout << (i++ == 0 ? "" : " ") << args), ...); cout << '\n'; } template void p1(const T1& a) { print_line(a); } template void p2(const T1& a, const T2& b) { print_line(a, b); } template void p3(const T1& a, const T2& b, const T3& c) { print_line(a, b, c); } template void p4(const T1& a, const T2& b, const T3& c, const T4& d) { print_line(a, b, c, d); } template void p5(const T1& a, const T2& b, const T3& c, const T4& d, const T5& e) { print_line(a, b, c, d, e); } template void print_range(const Container& values, string_view separator = " ") { bool first = true; for (const auto& value : values) { if (!first) cout << separator; first = false; cout << value; } cout << '\n'; } template void print(const vector& v) { print_range(v); } template void print(const vector>& v) { for (const auto& row : v) print_range(row); } #define VEC(type, name, size) vector name(size) #define VECI(type, name, size, init) vector name(size, init) #define VVEC(type, name, h, w) vector> name(h, vector(w)) #define VVECI(type, name, h, w, init) vector> name(h, vector(w, init)) #define VVVEC(type, name, d, h, w) vector>> name(d, vector>(h, vector(w))) #define VVVECI(type, name, d, h, w, init) vector>> name(d, vector>(h, vector(w, init))) #define VVVVEC(type, name, d1, d2, d3, d4) vector>>> name(d1, vector>>(d2, vector>(d3, vector(d4)))) #define VVVVECI(type, name, d1, d2, d3, d4, init) vector>>> name(d1, vector>>(d2, vector>(d3, vector(d4, init)))) #define VECP(type1, type2, name, size) vector> name(size) #define VECPI(type1, type2, name, size, init) vector> name(size, init) #define VP(type1, type2) vector> #define VVECP(type1, type2, name, h, w) vector>> name(h, vector>(w)) #define VVECPI(type1, type2, name, h, w, init) vector>> name(h, vector>(w, init)) #define VVP(type1, type2) vector>> #define VECT(type1, type2, type3, name, size) vector> name(size) #define VECTI(type1, type2, type3, name, size, init) vector> name(size, init) #define VT(type1, type2, type3) vector> template T SUM(const vector& v) { return accumulate(v.begin(), v.end(), (T)0); } template T MAX(const vector& v) { return *max_element(v.begin(), v.end()); } template T MIN(const vector& v) { return *min_element(v.begin(), v.end()); } template using min_pq = priority_queue, greater>; template using max_pq = priority_queue; template bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T& a, const T& b) { if (a > b) { a = b; return 1; } return 0; } template void uniq(vector& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); } template void dec(vector& a) { for (auto& x : a) x--; } bool in_range(int x, int y, int h, int w) { return x >= 0 && x < h && y >= 0 && y < w; } ll ceil_div(ll n, ll d) { assert(d != 0); assert(!(n == LLONG_MIN && d == -1)); ll q = n / d, r = n % d; if (r != 0 && ((r > 0) == (d > 0))) q++; return q; } ll floor_div(ll n, ll d) { assert(d != 0); assert(!(n == LLONG_MIN && d == -1)); ll q = n / d, r = n % d; if (r != 0 && ((r > 0) != (d > 0))) q--; return q; } // 精度ほぼ無限の平方根 long long integer_sqrt(long long N) { if (N <= 0) return 0; long long x = sqrt((long double)N); while ((__int128)(x + 1) * (x + 1) <= N) x++; while ((__int128)x * x > N) x--; return x; } // 文字列 s の idx 番目の文字を1つ削除した新しい文字列を返す // 使い方: S = erase_char(S, 3); string erase_char(string s, int idx) { if (idx < 0 || idx >= (int)s.length()) return s; // 範囲外アクセスの防止 s.erase(s.begin() + idx); return s; } // 文字列 s の idx 番目に文字 c を挿入した新しい文字列を返す // 使い方: S = insert_char(S, 3, 'a'); string insert_char(string s, int idx, char c) { if (idx < 0) idx = 0; if (idx > (int)s.length()) idx = s.length(); s.insert(s.begin() + idx, c); return s; } // アルファベットの大文字・小文字を反転させる関数 inline char flip_char(char c) { if (islower(c)) return toupper(c); if (isupper(c)) return tolower(c); return c; // アルファベット以外が来た場合はそのまま返す } long long count_digit_numbers(long long N, int d) { __int128 L = P10[d - 1]; __int128 R = P10[d] - 1; if ((__int128)N < L) return 0; __int128 upper = min((__int128)N, R); return (long long)(upper - L + 1); } // 中心 (sr, sc) からマンハッタン距離 dist にある、 // 行 i 上の列 j を最大2個返す。 // 存在しない候補は -1。 // // 戻り値: // res[0] = 左側の候補 // res[1] = 右側の候補 // // 左右が同じ点になる場合は res[1] = -1 とする。 array manhattan_columns( int W, int sr, int sc, int dist, int i ) { int remain = dist - abs(i - sr); // この行には距離 dist の点が存在しない if (remain < 0) { return {-1, -1}; } int left = sc - remain; int right = sc + remain; if (left < 0 || left >= W) { left = -1; } if (right < 0 || right >= W) { right = -1; } // remain == 0 のとき左右は同じ点 if (left == right) { right = -1; } return {left, right}; } template T GCD(const vector& v) { T res = 0; for (T x : v) res = std::gcd(res, x); return res; } template T LCM(const vector& v) { T res = 1; for (T x : v) res = std::lcm(res, x); return res; } template void extend(vector& a, const vector& b) { a.insert(a.end(), b.begin(), b.end()); } template void double_vec(vector& a) { int n = a.size(); a.reserve(n * 2); for(int i = 0; i < n; i++) a.push_back(a[i]); } template ll len(const T& x) { return (ll)x.size(); } long long nC2(long long n) { return n < 2 ? 0 : (ll)((int128)n * (n - 1) / 2); } long long nC3(long long n) { return n < 3 ? 0 : (ll)((int128)n * (n - 1) * (n - 2) / 6); } #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif #pragma endregion using m1 = atcoder::static_modint<1>; int main() { //※※積の問題の0除算 文字列ですべて同じ文字パターン オーバーフロー //※※ifの配列外参照を対策するなら初めに書かないとダメ 対角線は両方チェック //※※bit演算は比較演算子より後に計算されるから同時に使うときは()つける //※※ループの中で配列を宣言しない(外で宣言して使いまわす) //※※範囲for文で文字列、配列を受け取るときfor (auto& row : grid)のように&つけて参照渡し //※※2^63→ほぼ10^19(他は2^10を10^3とすると楽),log2は10^xのxを10/3する(10^18→60) //※※int:~10^9 ll:~10^18 int128:~10^38 //※※DFSはバックトラックが遅い!戻らなければO(N+M)。(BFSも同じ) //※※辞書順は貪欲法!絶対後戻りしないようにする //※※整数の平方根を使うならinteger_sqrtを使う! //※※制約最大が小さい2次元DP/累積和は static int A[505][505] など固定長配列が速いことがある //※※値はintで足りるか確認し、答えだけllにする。大きい配列はグローバル/staticに置く //※※内側ループは固定できる差分をB配列などに前計算して、配列アクセスと計算を減らす std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); auto start_time = chrono::steady_clock::now(); ll H,W; cin>>H>>W; ll A,B; cin>>A>>B; A--,B--; ll R1,C1,R2,C2; cin>>R1>>C1>>R2>>C2; R1--,C1--,R2--,C2--; ll P,Q; cin>>P>>Q; P--,Q--; // グリッド上のBFS (最短手数) VVVECI(int, dist, H, W,3, -1); queue> que; dist[A][B][0] = 0; if(R1<=A&&A<=R2&&C1<=B&&B<=C2){ if(A==P&&B==Q){ p1(0); return 0; } dist[A][B][1]=0; que.push({A, B,1}); }else{ que.push({A,B,0}); } while (!que.empty()) { auto [h, w,d] = que.front(); que.pop(); rep(dir, 0, 4) { int nh = h + dy[dir], nw = w + dx[dir]; ll nd=d; if(R1<=nh&&nh<=R2&&C1<=nw&&nw<=C2){ chmax(nd,1LL); } if(nd==1&&nh==P&&nw==Q){ nd=2; } if (!in_range(nh, nw, H, W)) continue; if (dist[nh][nw][nd] != -1) continue; // 訪問済み dist[nh][nw][nd] = dist[h][w][d] + 1; que.push({nh, nw,nd}); } } p1(dist[A][B][2]); auto end_time = chrono::steady_clock::now(); auto duration = chrono::duration_cast(end_time - start_time); cerr << "Execution Time: " << duration.count() << " ms" << endl; return 0; } /* */