Здравствуйте, Евтеев Алексей Николаевич.
Текст программы прилагается. Тестирование производилось на значениях 1..36 (до миллиарда как-то грустно тестировать). Путь всегда прокладывается в направлении N -> M (N >= M).

Приложение:
Uses
Crt;
Const
ifn = 'input.txt';
ofn = 'output.txt';
Var
M, N, i, path, ml, nl: Longint;
fn: Text;

procedure loadParams;
var
st: String;
code: integer;
temp: Longint;
begin
Assign(fn, ifn);
Reset(fn);
Readln(fn, st);
Close(fn);

Writeln(st);
Val(Copy(st, 1, pos(' ', st) - 1), M, code);
Delete(st, 1, pos(' ', st) - 1);
While (pos(' ', st) = 1) do
Delete(st, 1, 1);
Val(Copy(st, 1, length(st)), N, code);
if (M > N) then begin
temp := M;
M := N;
N := temp;
end;
ml := Trunc(Sqrt(M));
if (Sqr(ml) < M) then
Inc(ml);
nl := Trunc(Sqrt(N));
if (Sqr(nl) < N) then
Inc(nl);
Writeln('M = ', M, ', ml = ', ml);
Writeln('N = ', N, ', nl = ', nl);
end;

procedure saveResult;
begin
Assign(fn, ofn);
Rewrite(fn);
Write(fn, path);
Close(fn);
end;

procedure findPath(m, n: Longint; var path: Longint);
begin
Write(n);
if (m = n) then begin
Writeln;
end else begin
Write(' -> ');
Inc(path);
if (n = Sqr(Trunc(Sqrt(n)))) or ((ml = nl) and (n > m)) then begin
findPath(m, n - 1, path);
Exit;
end;
if (n = Sqr(Trunc(Sqrt(n))) + 1) or ((ml = nl) and (n < m)) then begin
findPath(m, n + 1, path);
Exit;
end;
if Odd(Sqr(nl) - n) then begin
Dec(nl);
Dec(n, 2*nl);
findPath(m, n, path);
end else begin
if ((m-Sqr(ml-1) < n-Sqr(nl-1))) then
findPath(m, n - 1, path)
else
findPath(m, n + 1, path)
end;
end;
end;

begin
ClrScr;
loadParams;
path := 0;
findPath(M, N, path);
Writeln('Length of path: ', path);
saveResult;
Write('Done. Press any key...');
readkey;
end.