Uses
	Dos,
	Graph;

Const
	MaxSteps	= 40;

Type
	MatrixNode = record
			Weight,
			Weight01,
			Weight10,
			Weight11	: double;
		end;
	CourseNode = record
			X,Y : Integer;
		end;
	Course = array[0..MaxSteps*2] of CourseNode;

Var
	nMarshroot, nMarshrootHigh: Longint;
	H0, V0, H1, V1: double;
	nSteps: Integer;
	Matrix: array[0..MaxSteps,0..MaxSteps] of MatrixNode;
	CurCourse,
	MinCourse,
	SavedCourse : Course;
	bHaveSaved: Boolean;
	i, j, k, l: integer;
	DeltaH, DeltaV, CurV, CurH : double;
	GraphDelta: Integer;
	MinWeight: double;

Label
	eRepeat;

function CalcWeiht( h0, v0, h1, v1: double ): double;
begin
	CalcWeiht := random;
end;

procedure StartGraph;
var
	grDriver: Integer;
	grMode: Integer;
	ErrCode: Integer;
	i, j : Integer;
	TempStr: String[16];
begin
	grDriver := Detect;
	InitGraph( grDriver, grMode, 'egavga.bgi' );
	if GraphResult <> grOk then Halt(1);

	Line( 64, 0, 64, 460 );
	Line( 60, 4, 64, 0 );
	Line( 64, 0, 68, 4 );
	Line( 64, 460, 639, 460 );
	Line( 635, 456, 639, 460 );
	Line( 639, 460, 635, 464 );

	SetColor( 11 );
	SetTextJustify( CenterText, TopText );
	OutTextXY( 32, 0, 'Высота,' );
	OutTextXY( 32, 8, 'метры' );
	OutTextXY( 600, 464, 'Скорость,' );
	OutTextXY( 600, 472, 'км/ч' );

	{ Нарисуем сетку - сначала вертикальную...}
	SetTextJustify( RightText, CenterText );
	for i := 0 to nSteps do begin
		SetColor( 15 );
		Line( 60, 460 - i * GraphDelta, 64, 460 - i * GraphDelta );
		if	( nSteps <= 15 ) or ( i = nSteps ) or
			( ( nSteps <= 30 ) and ( ( i mod 2 ) = 0 ) ) or
			( ( i mod 4 ) = 0 ) then begin
			Str( ( H0 + i * DeltaH ) : 4 : 0, TempStr );
			OutTextXY( 59, 460 - i * GraphDelta, TempStr );
		end;
		if i > 0 then begin
			SetColor( 8 );
			Line( 65, 460 - i * GraphDelta, 64 + nSteps * GraphDelta, 460 - i * GraphDelta );
		end;
	end;

	{ Теперь горизонтальную...}
	SetTextJustify( CenterText, TopText );
	for i := 0 to nSteps do begin
		SetColor( 15 );
		Line( 64 + i * GraphDelta, 460, 64 + i * GraphDelta, 464 );
		if	( nSteps <= 10 ) or ( i = nSteps ) or
			( ( nSteps <= 24 ) and ( ( i mod 2 ) = 0 ) ) or
			( ( i mod 4 ) = 0 ) then begin
			Str( ( V0 + i * DeltaV ) : 3 : 0, TempStr );
			OutTextXY( 64 + i * GraphDelta, 466, TempStr );
		end;
		if i > 0 then begin
			SetColor( 8 );
			Line( 64 + i * GraphDelta, 460 - nSteps * GraphDelta, 64 + i * GraphDelta, 459 );
		end;
	end;

end;

procedure IntDrawCourse( Var sCourse: Course; bDraw: Boolean );
Var
	i, x0, y0, x1, y1: integer;
begin
	i := 0;
	repeat
		x0 := 64 + sCourse[i].x * GraphDelta;
		y0 := 460 - sCourse[i].y * GraphDelta;
		x1 := 64 + sCourse[i+1].x * GraphDelta;
		y1 := 460 - sCourse[i+1].y * GraphDelta;
		if bDraw then begin
			SetColor( 14 );
			Line( x0, y0, x1, y1 );
		end else begin
			if ( x0 = x1 ) or ( y0 = y1 ) then begin
				if	( ( x0 = 64 ) and ( x0 = x1 ) ) or
					( ( y0 = 460 ) and ( y0 = y1 ) ) then
					SetColor( 15 )
				else
					SetColor( 8 );
				Line( x0, y0, x1, y1 );
				if ( x0 = 64 ) or ( y0 = 460 ) then PutPixel( x0, y0, 15 );
			end else begin
				SetColor( 0 );
				Line( x0 + 1, y0 - 1, x1 - 1, y1 + 1 );
				PutPixel( x1, y1, 8 );
				if ( x0 = 0 ) or ( y0 = 0 ) then
					PutPixel( x1, y1, 15 )
				else
					PutPixel( x1, y1, 8 );
			end
		end;
		i := i + 1;
	until ( sCourse[i].x = nSteps ) and ( sCourse[i].y = nSteps );
end;

procedure DrawCourse;
begin
	if bHaveSaved then IntDrawCourse( SavedCourse, False );
	SavedCourse := CurCourse;
	bHaveSaved := True;
	IntDrawCourse( CurCourse, True );
end;

Const
	StartTime :LongInt = 24 * 60 * 60;

function IntTime: Longint;
var
	h, m, s, hund : Word;
	Time: Longint;
begin
	GetTime( h, m, s, hund );
	Time := ( Longint( h ) * 60 + LongInt( m ) ) * 60 + LongInt( s );
	while Time < StartTime do Time := Time + 24 * 60 * 60;
	IntTime := Time;
end;

Const
	PrevTime: Longint = -1;

procedure IncrementMarchroot( Draw: Boolean );
Var
	S1, S2: String[64];
	t: Longint;
begin
	if not Draw then begin
		nMarshroot := nMarshroot + 1;
		if nMarshroot >= 1000000000 then begin
			nMarshrootHigh := nMarshrootHigh + 1;
			nMarshroot := 0;
		end;
	end;
	if Draw or ( ( nMarshroot mod 100000 ) = 0 ) then begin
		{ Напишем надпись }
		SetTextJustify( CenterText, TopText );
		if nMarshroot = 0 then begin
			SetColor( 13 );
			OutTextXY( 560, 10, 'Проверено маршрутов:' );
		end;
		Str( nMarshroot, S1 );
		if nMarshrootHigh > 0 then begin
			while Length( S1 ) < 9 do S1 := '0' + S1;
			Str( nMarshrootHigh, S2 );
			S1 := S2 + S1;
		end;
		SetFillStyle( SolidFill, 0 );
		Bar( 440, 22, 639, 32 );
		SetColor( 11 );
		OutTextXY( 560, 22, S1 );

		t := IntTime;
		if Draw or ( PrevTime <> t ) then begin
			PrevTime := t;
			t := t - StartTime;
			Str( t mod 60, s1 );
			if length( s1 ) < 2 then s1 := '0' + s1;
			Str( ( t div 60 ) mod 60, s2 );
			if length( s2 ) < 2 then s2 := '0' + s2;
			s1 := s2 + ':' + s1;
			Str( t div (24 * 60), s2 );
			if length( s2 ) < 2 then s2 := '0' + s2;
			s1 := s2 + ':' + s1;

			SetTextJustify( CenterText, TopText );
			if Draw then begin
				SetColor( 13 );
				OutTextXY( 560, 40, 'Прошло времени:' );
				OutTextXY( 560, 70, 'Маршрутов/секунду:' );
			end;
			SetFillStyle( SolidFill, 0 );
			SetColor( 11 );
			Bar( 480, 52, 639, 62 );
			OutTextXY( 560, 52, S1 );
			Bar( 480, 82, 639, 92 );
			if t <> 0 then begin
				Str( ( nMarshrootHigh * 1000000000.0 + nMarshroot ) / t : 9 : 0, S1 );
				OutTextXY( 560, 82, S1 );
			end;
		end;
	end;
end;

procedure CalcMinWeight( CurStep, x, y: Integer; CurWeight: double );
begin
	CurCourse[CurStep].x := x;
	CurCourse[CurStep].y := y;
	if Matrix[x,y].Weight < 0.0 then
		Matrix[x,y].Weight := CurWeight
	else begin
		if CurWeight > Matrix[x,y].Weight then begin
			IncrementMarchroot( False );
			Exit;
		end;
	end;

	if ( x = nSteps ) and ( y = nSteps ) then begin
		{ Дошло до конца! }
		IncrementMarchroot( False );
		if ( MinWeight < 0 ) or ( CurWeight < MinWeight ) then begin
			MinWeight := CurWeight;
			MinCourse := CurCourse;
			DrawCourse;
		end;
		exit;
	end;
	if ( x < nSteps ) and ( y < nSteps ) then
		CalcMinWeight( CurStep + 1, x + 1, y + 1, CurWeight + Matrix[x,y].Weight11 );

	if x < nSteps then
		CalcMinWeight( CurStep + 1, x + 1, y, CurWeight + Matrix[x,y].Weight01 );

	if y < nSteps then
		CalcMinWeight( CurStep + 1, x, y + 1, CurWeight + Matrix[x,y].Weight10 );
end;

begin
	Randomize;
	bHaveSaved := False;

	for i := 0 to MaxSteps do
		for j := 0 to MaxSteps do
			with Matrix[i,j] do begin
				Weight		:= -1.0;
				Weight01	:= 0.0;
				Weight10	:= 0.0;
				Weight11	:= 0.0;
			end;
	Write( 'H0 = ' );ReadLn( H0 );
	Write( 'V0 = ' );ReadLn( V0 );
	Write( 'H1 = ' );ReadLn( H1 );
	Write( 'V1 = ' );ReadLn( V1 );

eRepeat:
	Write( 'Steps = ' );ReadLn( nSteps );
	if( nSteps < 5 ) or ( nSteps > MaxSteps ) then begin
		writeln( 'Steps от 5 до ', Maxsteps, '!' );
		goto eRepeat;
	end;

	writeln( 'Идет расчет матрицы...' );
	GraphDelta := 400 div nSteps;
	DeltaH := ( H1 - H0 ) / nSteps;
	DeltaV := ( V1 - V0 ) / nSteps;
	for i := 0 to MaxSteps do begin
		CurV := V0 + i * DeltaV;
		for j := 0 to MaxSteps do begin
			CurH := H0 + j * DeltaH;
			with Matrix[i,j] do begin
				Weight01 := CalcWeiht( CurH, CurV, CurH, CurV + DeltaV );
				Weight10 := CalcWeiht( CurH, CurV, CurH + DeltaH, CurV );
				Weight11 := CalcWeiht( CurH, CurV, CurH + DeltaH, CurV + DeltaV );
			end;
		end;
	end;

	StartGraph;

	nMarshroot := -1;
	nMarshrootHigh := 0;
	IncrementMarchroot( True );
	MinWeight := -1.0;
	StartTime := IntTime;

	CalcMinWeight( 0, 0, 0, 0.0 );
	IncrementMarchroot( True );

	ReadLn;
end.