{ Условие: http://evatutin.narod.ru/evatutin_olymp_2014.pdf, http://evatutin.narod.ru/mathhelper.html } { Автор решения: Ватутин Э.И., http://evatutin.narod.ru, evatutin@rambler.ru } { Время, затраченное на решение: 33 минуты } program Task2; {$APPTYPE CONSOLE} type { Матрица } TMatrix = array of array of Integer; { Маршрут } // Замечание: можно обойтись списком вместо двумерного массива! TWay = array of array of Boolean; { Направление, из которого в ячейку пришел текущий кратчайший путь } TDirection = (drUnknown, drFromTop, drFromLeft); { Параметры ячейки матрица } TCell = record Visited: Boolean; { Достигнута ли ячейки } CurrPathLen: Integer; { Длина кратчайшего пути до ячейки } From: TDirection; { Откуда пришел кратчайший путь } end; TCells = array of array of TCell; procedure FindWay(const M: TMatrix; var W: TWay; var L: Integer); var C: TCells; I, J: Integer; Changed: Boolean; CurrX, CurrY: Integer; begin SetLength(C, Length(M), Length(M)); { Исходная информация: ни одна ячейка не посещена } for I := 0 to High(C) do for J := 0 to High(C) do with C[I][J] do begin Visited := False; CurrPathLen := High(Integer); { Заведомо большое значение } From := drUnknown; end; { Кроме верхней левой } with C[0][0] do begin Visited := True; CurrPathLen := M[0][0]; end; repeat Changed := False; { Просмотр ячеек таблицы, корректировка длин маршрутов } // Замечание вместо просмотра N^2 ячеек каждый раз можно организовать список, в котором хранить "волновой фронт" — список обновленных клеток с прошлого прохода! for I := 0 to High(M) do for J := 0 to High(M) do begin { Непосещенные клетки не рассматриваем } if not C[I][J].Visited then continue; { Шаг вправо } if (I < High(M)) and { Есть куда идти вправо } (C[I][J].CurrPathLen + M[I+1][J] < C[I+1][J].CurrPathLen) { Путь вправо короче предыдущего } then with C[I+1][J] do begin Visited := True; CurrPathLen := C[I][J].CurrPathLen + M[I+1][J]; From := drFromLeft; Changed := True; end; { Шаг вниз } if (J < High(M)) and { Есть куда идти вправо } (C[I][J].CurrPathLen + M[I][J+1] < C[I][J+1].CurrPathLen) { Путь вправо короче предыдущего } then with C[I][J+1] do begin Visited := True; CurrPathLen := C[I][J].CurrPathLen + M[I][J+1]; From := drFromTop; Changed := True; end; end; until not Changed; { Построение пути } CurrX := Length(M)-1; CurrY := Length(M)-1; SetLength(W, Length(M), Length(M)); for I := 0 to High(W) do for J := 0 to High(W) do W[I][J] := False; W[0][0] := True; while not ((CurrX = 0) and (CurrY = 0)) do begin W[CurrX][CurrY] := True; case C[CurrX][CurrY].From of drFromTop: CurrY := CurrY - 1; drFromLeft: CurrX := CurrX - 1; else ASSERT(False); end; end; { Длина пути } L := C[High(C)][High(C)].CurrPathLen; C := nil; end; procedure PrintWay(const W: TWay); var I, J: Integer; begin for I := 0 to High(W) do begin for J := 0 to High(W) do Write(Byte(W[I][J])); Writeln; end; end; { Исходные данные } var M: TMatrix; W: TWay; L: Integer; { Загрузка исходных данных } procedure LoadSourceData(); begin SetLength(M, 3, 3); M[0][0] := 9; M[0][1] := 4; M[0][2] := 3; M[1][0] := 2; M[1][1] := 1; M[1][2] := 6; M[2][0] := 0; M[2][1] := 9; M[2][2] := 1; end; begin { Загрузка исходных данных } LoadSourceData(); { Поиск решения } FindWay(M, W, L); { Вывод решения } Writeln(L); Writeln; PrintWay(W); Readln; end.