{  ACM International Collegiate Programming Contest
   Central European Regional Contest 2000
   
   Problem D - Direct Visibility
   Martin Kacer
}
   
Program Town;
Const MAX_SIZE = 512;
	CLIMB_UP   = 1;
	CLIMB_DOWN = 3;

{
COORDINATES:
centers of little squares have coordinates 1,3,5,7 etc.
square boundaries have coordinates 0,2,4,6,8 etc.
all variables with names X,Y,Z confirm to this coordinate system
all other variables are square indices: 1,2,3,4,5 etc.
zero point is in the top-left corner; X goes down, Y to the right
}

Var TaskCnt, TaskNum : Integer;
	Towers			 : Array [1..MAX_SIZE, 1..MAX_SIZE] of Integer;
	Rows, Cols, R, C : Integer;
	R1, C1, R2, C2	 : Integer;
	Reachable		 : Array [1..MAX_SIZE, 1..MAX_SIZE] of Boolean;
	Distance		 : Array [1..MAX_SIZE, 1..MAX_SIZE] of Integer;
	QueueB, QueueE	 : Integer;
	QueueR, QueueC	 : Array [1..(MAX_SIZE*MAX_SIZE)] of Integer;

{ the line (TX,TY,TZ)-(BX,BY,BZ) enters some square at coordinate X }
Function CheckXPos (TX, TY, TZ, BX, BY, BZ, X : Integer) : Boolean;
Var YxBXTX, Y	 : Integer;
	ZxBXTX, BXTX : Integer;
	R, C		 : Integer;
Begin
	{ Y = TY + (BY-TY) * (X-TX) / (BX-TX) }
	YxBXTX:= TY * (BX-TX) + (BY-TY) * (X-TX);
	ZxBXTX:= TZ * (BX-TX) + (BZ-TZ) * (X-TX);
	BXTX:= BX-TX;
	If (BXTX < 0) then Begin
		BXTX:= 0 - BXTX;
		YxBXTX:= 0 - YxBXTX;
		ZxBXTX:= 0 - ZxBXTX;
	End;
	If (BY < TY) then YxBXTX:= YxBXTX - 1;
	If (BX < TX) then X:= X - 1;
	R:= X div 2 + 1;
	C:= (YxBXTX div BXTX) div 2 + 1;
	{WriteLn ('DEBUG: R=',R,', C=',C,', Z=',ZxBXTX,'/',BXTX,', ret=',
			 (Towers[R,C] * BXTX > ZxBXTX));}
	CheckXPos:= (Towers[R,C] * BXTX * 2 > ZxBXTX);
End; { CheckXPos }

Function CheckYPos (TX, TY, TZ, BX, BY, BZ, Y : Integer) : Boolean;
Var XxBYTY, X	 : Integer;
	ZxBYTY, BYTY : Integer;
	R, C		 : Integer;
Begin
	{ X = TX + (BX-TX) * (Y-TY) / (BY-TY) }
	XxBYTY:= TX * (BY-TY) + (BX-TX) * (Y-TY);
	ZxBYTY:= TZ * (BY-TY) + (BZ-TZ) * (Y-TY);
	BYTY:= BY-TY;
	If (BYTY < 0) then Begin
		BYTY:= 0 - BYTY;
		XxBYTY:= 0 - XxBYTY;
		ZxBYTY:= 0 - ZxBYTY;
	End;
	If (BX < TX) then XxBYTY:= XxBYTY - 1;
	If (BY < TY) then Y:= Y - 1;
	R:= (XxBYTY div (BYTY)) div 2 + 1;
	C:= Y div 2 + 1;
	{WriteLn ('DEBUG: R=',R,', C=',C,', Z=',ZxBYTY,'/',BYTY,', ret=',
			 (Towers[R,C] * BYTY * 2 > ZxBYTY));}
	CheckYPos:= (Towers[R,C] * BYTY * 2 > ZxBYTY);
End; { CheckYPos }


{ TZ must be lower than BZ! }
Function IsVisibleLine (TX, TY, TZ, BX, BY, BZ : Integer) : Boolean;
Var X1, X2, Y1, Y2, XD, YD : Integer;
	Vis					   : Boolean;
Begin
	Vis:= true;
	{ walk in X-direction }
	If (TX < BX) then Begin
		X1:= (TX+1);
		X2:= (BX-1);
		XD:= 2;
	End else If (TX > BX) then Begin
		X1:= (TX-1);
		X2:= (BX+1);
		XD:= -2;
	End else Begin
		X1:= 0;
		X2:= 0;
		XD:= 0;
	End;
	While (X1-XD <> X2) and Vis do
	Begin
		If CheckXPos (TX, TY, TZ, BX, BY, BZ, X1) then Vis:= false;
		X1:= X1 + XD;
	End;

	{ walk in Y-direction }
	If (TY < BY) then Begin
		Y1:= (TY+1);
		Y2:= (BY-1);
		YD:= 2;
	End else If (TY > BY) then Begin
		Y1:= (TY-1);
		Y2:= (BY+1);
		YD:= -2;
	End else Begin
		Y1:= 0;
		Y2:= 0;
		YD:= 0;
	End;
	While (Y1-YD <> Y2) and Vis do
	Begin
		If CheckYPos (TX, TY, TZ, BX, BY, BZ, Y1) then Vis:= false;
		Y1:= Y1 + YD;
	End;

	IsVisibleLine:= Vis;
End;


{ visibility between two specific squares }
Function IsVisibleSquare (R1, C1, R2, C2 : Integer) : Boolean;
Begin
	If (Towers[R1,C1] < Towers[R2,C2]) then
		IsVisibleSquare:= IsVisibleLine
				(R1*2-1, C1*2-1, Towers[R1,C1]*2 + 1,
				 R2*2-1, C2*2-1, Towers[R2,C2]*2 + 1)
	else
		IsVisibleSquare:= IsVisibleLine
				(R2*2-1, C2*2-1, Towers[R2,C2]*2 + 1,
				 R1*2-1, C1*2-1, Towers[R1,C1]*2 + 1);
End; { IsVisibleSquare }


{ enqueues specified field if it is reachable }
Procedure Enqueue (R, C	: Integer; H, D : Integer);
Begin
	If (R >= 1) and (R <= Rows) and (C >= 1) and (C <= Cols) then
		If (Distance[R,C] = 0) and (Reachable[R,C])
				and (Towers[R,C] >= H - CLIMB_DOWN)
				and (Towers[R,C] <= H + CLIMB_UP) then
		Begin
			QueueE:= QueueE + 1;
			QueueR[QueueE]:= R;
			QueueC[QueueE]:= C;
			Distance[R,C]:= D+1;
		End;
End; { Enqueue }


Begin
	Readln (TaskCnt);
	For TaskNum:= 1 to TaskCnt do
	Begin
		ReadLn (Rows, Cols);
		For R:= 1 to Rows do Begin
			For C:= 1 to Cols do
				Read (Towers[R,C]);
			ReadLn;
		End;
		ReadLn (R1, C1, R2, C2);
		For R:= 1 to Rows do
			For C:= 1 to Cols do
				Reachable[R,C]:= IsVisibleSquare (R1, C1, R, C)
						or IsVisibleSquare (R2, C2, R, C);

		{WriteLn ('vvvvv ----- DEBUG ----- vvvvv');
		For R:= 1 to Rows do Begin
			For C:= 1 to Cols do
				If ((R=R1) and (C=C1)) or ((R=R2) and (C=C2)) then
					Write ('[', Towers[R,C], ']  ')
				else If Reachable[R,C] then
					Write ('(', Towers[R,C], ')  ')
				else
					Write (' ', Towers[R,C], '   ');
			WriteLn;
		End;
		WriteLn ('^^^^^ ----- DEBUG ----- ^^^^^');}

		For R:= 1 to Rows do For C:= 1 to Cols do Distance[R,C]:= 0;
		QueueB:= 0;
		QueueE:= 0;
		Enqueue (R1, C1, Towers[R1,C1], 0);
		While (QueueB < QueueE) and (Distance[R2,C2] = 0) do
		Begin
			QueueB:= QueueB + 1;
			R:= QueueR[QueueB];
			C:= QueueC[QueueB];
			Enqueue (R+1, C, Towers[R,C], Distance[R,C]);
			Enqueue (R-1, C, Towers[R,C], Distance[R,C]);
			Enqueue (R, C+1, Towers[R,C], Distance[R,C]);
			Enqueue (R, C-1, Towers[R,C], Distance[R,C]);
		End;
		If (Distance[R2,C2] = 0) then
			WriteLn ('Mission impossible!')
		else
			WriteLn ('The shortest path is ', Distance[R2,C2]-1, ' steps long.');
	End;
End.
