program direct; const Infinity = $3FFFFFFF; QSize = 201 * 201; DX: array [0..3] of Integer = (1, 0, -1, 0); DY: array [0..3] of Integer = (0, 1, 0, -1); var Visible: array [0..201, 0..201] of Byte; Z: array [0..201, 0..201] of Integer; function Beam(X1: Integer; Y1: Integer; X2: Integer; Y2: Integer) : Boolean; var MaxT: Integer; T: Integer; function Check(H: Integer): Boolean; begin Check := (MaxT - T) * (2 * Z[X1, Y1] + 1) + T * (2 * Z[X2, Y2] + 1) >= 2 * MaxT * H; end; var B: Boolean; DX: Integer; DY: Integer; StepX: Integer; StepY: Integer; T1: Integer; T2: Integer; X: Integer; Y: Integer; begin StepX := X2 - X1; StepY := Y2 - Y1; DX := Abs(StepX); DY := Abs(StepY); if DX = 0 then DX := 1 else StepX := StepX div DX; if DY = 0 then DY := 1 else StepY := StepY div DY; MaxT := 2 * DX * DY; T := 0; X := DY * (2 * X1 + 1); Y := DX * (2 * Y1 + 1); B := True; while T < MaxT do begin if StepX = 0 then T1 := Infinity else if StepX > 0 then T1 := 2 * DY - X mod (2 * DY) else begin T1 := X mod (2 * DY); if T1 = 0 then T1 := 2 * DY; end; if StepY = 0 then T2 := Infinity else if StepY > 0 then T2 := 2 * DX - Y mod (2 * DX) else begin T2 := Y mod (2 * DX); if T2 = 0 then T2 := 2 * DX; end; if T1 > MaxT - T then T1 := MaxT - T; if T2 > MaxT - T then T2 := MaxT - T; if T1 < T2 then begin Inc(T, T1); Inc(X, StepX * T1); Inc(Y, StepY * T1); end else begin Inc(T, T2); Inc(X, StepX * T2); Inc(Y, StepY * T2); end; if (X mod (2 * DY) <> 0) or (Y mod (2 * DX) <> 0) then begin { Writeln('beam ', X div (2 * DY), ' ', Y div (2 * DX), ' ', X mod (2 * DY), ' ', Y mod (2 * DX));} if X mod (2 * DY) = 0 then B := B and Check(Z[X div (2 * DY) , Y div (2 * DX)]) and Check(Z[X div (2 * DY) - 1, Y div (2 * DX)]) else if Y mod (2 * DX) = 0 then B := B and Check(Z[X div (2 * DY), Y div (2 * DX) ]) and Check(Z[X div (2 * DY), Y div (2 * DX) - 1]); end; if not B then Break; end; { if B then begin Visible[X2, Y2] := True; Writeln(X1, ' ', Y1, ' ', X2, ' ', Y2, ' are connected'); end; } Beam := B; end; var QTime: array [1..200, 1..200] of Integer; QX: array [0..QSize - 1] of Integer; QY: array [0..QSize - 1] of Integer; P: Integer; Q: Integer; QHead: Integer; QTail: Integer; function QEmpty: Boolean; begin QEmpty := QHead = QTail; end; procedure QGet(var X: Integer; var Y: Integer; var T: Integer); begin X := QX[QTail]; Y := QY[QTail]; T := QTime[X, Y]; Inc(QTail); QTail := QTail mod QSize; end; procedure QInit; var I: Integer; J: Integer; begin QHead := 0; QTail := 0; for I := 1 to P do for J := 1 to Q do QTime[I, J] := Infinity; end; procedure QPut(X: Integer; Y: Integer; T: Integer); begin if T < QTime[X, Y] then begin { Writeln('step ', X, ' ', Y, ' ', T);} QX[QHead] := X; QY[QHead] := Y; QTime[X, Y] := T; Inc(QHead); QHead := QHead mod QSize; end; end; var C: array [1..2] of Integer; R: array [1..2] of Integer; D: Integer; I: Integer; J: Integer; K: Integer; T: Integer; Time: Integer; X: Integer; Y: Integer; function Vis(X, Y: Integer): Boolean; begin if Visible[X, Y] = 0 then begin if Beam(R[1], C[1], X, Y) or Beam(R[2], C[2], X, Y) then Visible[X, Y] := 1 else Visible[X, Y] := 2; end; if Visible[X, Y] = 1 then Vis := True else Vis := False; end; begin Read(T); while T <> 0 do begin Dec(T); Read(P, Q); for I := 0 to P + 1 do for J := 0 to Q + 1 do Z[I, J] := Infinity; for I := 1 to P do for J := 1 to Q do Read(Z[I, J]); Read(R[1], C[1], R[2], C[2]); { for I := 1 to P do for J := 1 to Q do for K := 1 to 2 do Beam(R[K], C[K], I, J); } FillChar(Visible, SizeOf(Visible), 0); Visible[R[1], C[1]] := 1; Visible[R[2], C[2]] := 1; QInit; QPut(R[1], C[1], 0); while not QEmpty do begin QGet(I, J, Time); for D := 0 to 3 do if Vis(I + DX[D], J + DY[D]) and (Z[I + DX[D], J + DY[D]] - Z[I, J] <= 1) and (Z[I + DX[D], J + DY[D]] - Z[I, J] >= -3) then QPut(I + DX[D], J + DY[D], Time + 1); end; if QTime[R[2], C[2]] < Infinity then Writeln('The shortest path is ', QTime[R[2], C[2]], ' steps long.') else Writeln('Mission impossible!'); end; end.