/* -*- coding: utf-8 -*- * * 2213.cc: No.2213 Neq Move - yukicoder */ #include #include #include #include #include using namespace std; /* constant */ const int MAX_M = 3 + 4 * 2; const int MAX_N = MAX_M * MAX_M; const long long LINF = 1LL << 60; /* typedef */ using ll = long long; using pii = pair; using vpii = vector; using pli = pair; /* global variables */ vpii nbrs[MAX_N]; ll ds[MAX_N]; /* subroutines */ /* main */ int main() { int tn; scanf("%d", &tn); while (tn--) { int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); // a->c, b->d int as[MAX_M] = { 0, 1, 2, a, a + 1, b, b + 1, c, c + 1, d, d + 1 }; sort(as, as + MAX_M); int m = unique(as, as + MAX_M) - as; int n = m * m; int st = -1, gl = -1; for (int u = 0; u < n; u++) { nbrs[u].clear(); int ux = u / m, uy = u % m; if (ux == uy) continue; if (as[ux] == a && as[uy] == b) st = u; if (as[ux] == c && as[uy] == d) gl = u; for (int vx = ux + 1; vx < m; vx++) if (uy < ux || vx < uy) nbrs[u].push_back({as[vx] - as[ux], vx * m + uy}); for (int vy = uy + 1; vy < m; vy++) if (ux < uy || vy < ux) nbrs[u].push_back({as[vy] - as[uy], ux * m + vy}); if (ux != 0 && uy != 0) { nbrs[u].push_back({1, ux * m + 0}); nbrs[u].push_back({1, 0 * m + uy}); } } //for (int i = 0; i < m; i++) printf(" %d", as[i]); putchar('\n'); //printf(" st=%d, gl=%d\n", st, gl); fill(ds, ds + n, LINF); ds[st] = 0; priority_queue q; q.push({0, st}); while (! q.empty()) { auto [ud, u] = q.top(); q.pop(); ud = -ud; if (ds[u] != ud) continue; for (auto [e, v]: nbrs[u]) { ll vd = ud + e; if (ds[v] > vd) { ds[v] = vd; q.push({-vd, v}); } } } printf("%lld\n", ds[gl]); } return 0; }