#include using namespace std; #define REP(i, n) for(int i=0; i<(n); ++i) #define FOR(i, a, b) for(int i=(a); i<=(b); ++i) #define FORD(i, a, b) for(int i=(a); i>=(b); --i) #define ll long long #define vi vector #define pii pair #define pdd pair #define mp make_pair #define X first #define Y second const int INF = 1<<29; #define EPS 0.00000000001 int T; int N, M; int z[205][205]; int dist[205][205]; pii A, B; bool visible[205][205]; pdd square[4] = {mp(-0.5, -0.5), mp(-0.5, 0.5), mp(0.5, 0.5), mp(0.5, -0.5)}; queue< pii > que; bool outside(pii A) { return A.X < 0 || A.X >= N || A.Y < 0 || A.Y >= M; } double _distance(pdd A, pdd B) { return sqrt((A.X - B.X) * (A.X - B.X) + (A.Y - B.Y) * (A.Y - B.Y)); } bool eqi(double x, double y) { return abs(x - y) < EPS; } bool eqi(pdd x, pdd y) { return _distance(x, y) < EPS; } bool point_on_segment(pdd P, pair< pdd, pdd > A) { if (eqi(P, A.X) || eqi(P, A.Y)) return true; A = mp(min(A.X, A.Y), max(A.X, A.Y)); pdd p1 = A.X; pdd p2 = A.Y; bool ok1, ok2, ok3; ok1 = p1.X <= P.X && P.X <= p2.X; ok2 = (p1.Y <= P.Y && P.Y <= p2.Y) || (p1.Y >= P.Y && P.Y >= p2.Y); return ok1 && ok2; } pdd intersect(pair< pdd, pdd > a, pair< pdd, pdd > b) { double x1 = a.X.X, y1 = a.X.Y; double x2 = a.Y.X, y2 = a.Y.Y; double x3 = b.X.X, y3 = b.X.Y; double x4 = b.Y.X, y4 = b.Y.Y; double den = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); return mp( ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / den, ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / den); } bool vis(pii Ai, pii Bi) { pdd A = Ai, B = Bi; pair< pdd, pdd > line1 = mp(A, B); if (Ai.X == Bi.X) { int i = Ai.X; FOR(j, min(Ai.Y, Bi.Y), max(Ai.Y, Bi.Y)) { if (eqi(A, mp((double)i, (double)j)) || eqi(B, mp((double)i, (double)j))) continue; vector< pdd > inters; REP (k, 4) { pair< pdd, pdd > line2 = mp(mp(i + square[k].X, j + square[k].Y), mp(i + square[(k + 1) % 4].X, j + square[(k + 1) % 4].Y)); pdd inter = intersect(line1, line2); if (point_on_segment(inter, line1) && point_on_segment(inter, line2)) { inters.push_back(inter); } } if (inters.size() < 2) continue; if (_distance(inters[0], inters[1]) < EPS) continue; REP(k, inters.size()) { pdd inter = inters[k]; double expected_z = z[Ai.X][Ai.Y] + 0.5 + (z[Bi.X][Bi.Y] - z[Ai.X][Ai.Y]) * _distance(inter, A) / _distance(A, B); if (z[i][j] > expected_z + EPS) { return false; } } } } else { FOR(i, min(Ai.X, Bi.X), max(Ai.X, Bi.X)) { REP(ji, 2) { int j = A.Y + (B.Y - A.Y) * (i - A.X) / (B.X - A.X) + ji; if (j < 0 || j >= M) continue; if (eqi(A, mp((double)i, (double)j)) || eqi(B, mp((double)i, (double)j))) continue; vector< pdd > inters; REP (k, 4) { pair< pdd, pdd > line2 = mp(mp(i + square[k].X, j + square[k].Y), mp(i + square[(k + 1) % 4].X, j + square[(k + 1) % 4].Y)); pdd inter = intersect(line1, line2); if (point_on_segment(inter, line1) && point_on_segment(inter, line2)) { inters.push_back(inter); } } if (inters.size() < 2) continue; if (_distance(inters[0], inters[1]) < EPS) continue; REP(k, inters.size()) { pdd inter = inters[k]; double expected_z = z[Ai.X][Ai.Y] + 0.5 + (z[Bi.X][Bi.Y] - z[Ai.X][Ai.Y]) * _distance(inter, A) / _distance(A, B); if (z[i][j] > expected_z + EPS) { return false; } } }}} return true; } int main() { scanf("%d", &T); while (T--) { scanf("%d%d", &N, &M); REP(i, N) REP(j, M) { scanf("%d", &z[i][j]); dist[i][j] = INF; } scanf("%d%d%d%d", &A.X, &A.Y, &B.X, &B.Y); --A.X; --A.Y; --B.X; --B.Y; REP(i, N) REP(j, M) { visible[i][j] = (vis(mp(i, j), A) || vis(mp(i, j), B)); } while (!que.empty()) que.pop(); que.push(A); dist[A.X][A.Y] = 0; while (!que.empty()) { pii now = que.front(); que.pop(); // printf("now (%d, %d), dist %d, vyska %d\n", now.X, now.Y, dist[now.X][now.Y], z[now.X][now.Y]); if (now == B) break; FOR(dx, -1, 1) FOR(dy, -1, 1) if (dx * dx + dy * dy == 1) { pii p = mp(now.X + dx, now.Y + dy); if (outside(p) || z[p.X][p.Y] > z[now.X][now.Y] + 1 || z[p.X][p.Y] < z[now.X][now.Y] - 3 || !visible[p.X][p.Y] || dist[p.X][p.Y] != INF) continue; dist[p.X][p.Y] = dist[now.X][now.Y] + 1; que.push(p); } } if (dist[B.X][B.Y] != INF) { printf("The shortest path is %d steps long.\n", dist[B.X][B.Y]); } else { printf("Mission impossible!\n"); } } return 0; }