#include #define soclose 1e-8 using namespace std; struct pt { double x,y,z; }; double getY(double X, pt &A, pt &B) { return A.y-(A.x-X)*(A.y-B.y)/(A.x-B.x);} double getX(double Y, pt &A, pt &B) { return A.x-(A.y-Y)*(A.x-B.x)/(A.y-B.y);} double getZx(double X, pt &A, pt &B) { return A.z+(X-A.x)*(A.z-B.z)/(A.x-B.x);} double getZy(double Y, pt &A, pt &B) { return A.z+(Y-A.y)*(A.z-B.z)/(A.y-B.y);} int main() { int T; cin >> T; for(int t =0; t < T; t++) { int R,C; cin >> R >> C; vector< vector > H(R,vector(C)); for(int i =0; i < R*C; i++) cin >> H[i/C][i%C]; vector< vector > F(R,vector(C,false)); pair P[2]; for(int k =0; k < 2; k++) { cin >> P[k].first >> P[k].second; P[k].first -=1; P[k].second -=1;} if(P[0].first == P[1].first && P[0].second == P[1].second) { cout << "The shortest path is 0 steps long.\n"; continue;} for(int i =0; i < R; i++) for(int j =0; j < C; j++) for(int k =0; k < 2; k++) { if(P[k].first == i && P[k].second == j) {F[i][j] =true; continue;} bool ok =true; pt A; A.x =i+0.5; A.y =j+0.5, A.z =H[i][j]+0.5; pt B; B.x =P[k].first+0.5; B.y =P[k].second+0.5, B.z =H[P[k].first][P[k].second]+0.5; if(P[k].first != i) { for(int x =min(i,P[k].first)+1; x < max(i,P[k].first); x++) { double y =getY(x,A,B); double z =getZx(x,A,B); int Y =(int)(y+soclose); if(abs(y-round(y)) < soclose) continue; if(H[x+1][Y]-soclose >= z) ok =false; if(H[x][Y]-soclose >= z) ok =false;} } if(P[k].second != j) { for(int y =min(j,P[k].second)+1; y < max(j,P[k].second); y++) { double x =getX(y,A,B); double z =getZy(y,A,B); int X =(int)(x+soclose); if(abs(x-round(x)) < soclose) continue; if(H[X][y+1]-soclose >= z) ok =false; if(H[X][y]-soclose >= z) ok =false;} } if(ok) F[i][j] =true;} queue< pair > q; int dx[] ={0,0,1,-1}; int dy[] ={1,-1,0,0}; q.push(P[0]); vector< vector > D(R,vector(C,R*C+42)); D[P[0].first][P[0].second] =0; while(!q.empty()) { pair p =q.front(); for(int k =0; k < 4; k++) if(min(p.first+dx[k],p.second+dy[k]) >= 0 && p.first+dx[k] < R && p.second+dy[k] < C) if(F[p.first+dx[k]][p.second+dy[k]] && H[p.first][p.second]+1 >= H[p.first+dx[k]][p.second+dy[k]] && H[p.first][p.second]-3 <= H[p.first+dx[k]][p.second+dy[k]] && D[p.first+dx[k]][p.second+dy[k]] > D[p.first][p.second]+1) { D[p.first+dx[k]][p.second+dy[k]] =D[p.first][p.second]+1; q.push(make_pair(p.first+dx[k],p.second+dy[k]));} q.pop();} if(D[P[1].first][P[1].second] > R*C) cout << "Mission impossible!\n"; else cout << "The shortest path is " << D[P[1].first][P[1].second] << " steps long.\n";} }