Лабиринт Тезея найти кратчайший путь возвращения

[Izobara]

Тезей вышел из лабиринта Кентавра с помощью нитки. Вы можете использовать компьютер.
Вам дан путь Тезея:
N - один шаг на север
S - один на юг
W - один на запад
E - один на восток
Найти самый короткий путь назад. Учтите, что идти можно только по пути Тезея, не срезая и не скорачивая.
Пример: - EENNESWSSWE вывести NWW
Я пытался, но по-моему, как раз срезаю иногда. Собственно, в этом проблемма. Обратите внимание, что идти надо ТОЛЬКО по пути Тезея. У меня это не реализовано. Помогите доделать. Чтоб лучше понять, нарисуйте путь из примера на координатной плоскости.

var
 ch:char;
 S:string;
  x,y:integer;
  begin
   assign(input,'maze.in');
   reset(input);
   assign(output,'maze.out');
   rewrite(output);
    While (not eoln) do
     begin
      Read(ch);
      case ch of
      'N': inc(y);
      'S': dec(y);
      'E': inc(x);
      'W': dec(x);
      end;
     end;
      while x<>0 do
       begin
       if x>0 then
        begin
         s:='W'+S; dec(x);
        end;
        if x<0 then
        begin
         s:='E'+s; inc(x);
        end;
       end;
       while y<> 0 do
        begin
        if y>0 then
        begin
         s:='S'+s; dec(y);
        end;
        if y<0 then
        begin
         s:='N'+s; inc(y);
        end;
       end;
     Writeln(s);
  close(input);
  close(output);
  end.

[Abstraction]

"По пути" - это "проходя только через уже посещённые клетки" или "проходя только между теми клетками, между которыми уже проходили"?

[Izobara]

Он идет по нитке, которую протянул. Видимо, по тому же пути, только назад. Он круги наматывает. Надо вывести типо шаг на север, шаг на юг - одной буквой.

[BDA]

Сразу бы написали номер задачи (адрес), чтобы было понятно, где тестировать (люблю тестировать).
http://acmp.ru/?main=task&id_task=459

Update 22:11
Пока 7 тестов из 8

const
  N = 1;
  E = 2;
  S = 4;
  W = 8;

type
  arr = array [-200 .. 200, -200 .. 200] of integer;

var
  a: arr;
  i, j, k: integer;
  c: char;

procedure startsearch(var a: arr; x, y, lvl: integer);
begin
  if (x > 200) or (y > 200) or (x < -200) or (y < -200) or (a[y, x] = 0) or
    (a[y, x] shr 4 <> 0) then
    exit;
  a[y, x] := a[y, x] or (lvl shl 4);
  startsearch(a, x + 1, y, lvl + 1);
  startsearch(a, x, y + 1, lvl + 1);
  startsearch(a, x - 1, y, lvl + 1);
  startsearch(a, x, y - 1, lvl + 1);
end;

procedure printpath(const a: arr; x, y: integer);
var
  lvl: integer;
begin
  lvl := a[y, x] shr 4;
  if (a[y, x] and W > 0) and (a[y, x - 1] shr 4 = lvl - 1) then
  begin
    printpath(a, x - 1, y);
    write('E');
    exit;
  end;
  if (a[y, x] and S > 0) and (a[y - 1, x] shr 4 = lvl - 1) then
  begin
    printpath(a, x, y - 1);
    write('N');
    exit;
  end;
  if (a[y, x] and E > 0) and (a[y, x + 1] shr 4 = lvl - 1) then
  begin
    printpath(a, x + 1, y);
    write('W');
    exit;
  end;
  if (a[y, x] and N > 0) and (a[y + 1, x] shr 4 = lvl - 1) then
  begin
    printpath(a, x, y + 1);
    write('S');
    exit;
  end;
end;

begin
  assign(input, 'input.txt');
  reset(input);
  assign(output, 'output.txt');
  rewrite(output);
  for i := -200 to 200 do
    for j := -200 to 200 do
      a[i, j] := 0;
  i := 0;
  j := 0;
  while not EOF do
  begin
    read(c);
    case c of
      'N':
        begin
          a[i, j] := a[i, j] or N;
          inc(i);
          a[i, j] := a[i, j] or S;
        end;
      'E':
        begin
          a[i, j] := a[i, j] or E;
          inc(j);
          a[i, j] := a[i, j] or W;
        end;
      'S':
        begin
          a[i, j] := a[i, j] or S;
          dec(i);
          a[i, j] := a[i, j] or N;
        end;
      'W':
        begin
          a[i, j] := a[i, j] or W;
          dec(j);
          a[i, j] := a[i, j] or E;
        end;
    end;
  end;
  startsearch(a, j, i, 1);
  printpath(a, 0, 0);
end.

[Izobara]

Она была у нас на олимпиаде. Не знал, что там есть.

[Izobara]

Сообщение от BDA

Пока 7 тестов из 8

На сервере моей олимпиады проходит 6 из 12...
Например, если на входе ENESWSESSWNEE, то что-то не то.

[BDA]

Так у Вас есть ответы?)
Если есть, то выложите парочку.

Мне кажется, я нашел изъян в своем поиске (осталось его исправить).

Хм, все же там что-то более серьезное (в программе), т.к. пока я предполагаю ошибку выбора не того маршрута (из нескольких подходящих), а по логам получается, что находится не самый короткий маршрут.

Кстати, визуализация 12 теста
(красный - начало пути, голубой - конец)

[Izobara]

У меня только лог ошибок - правильных ответов там нет.
Смотри в файле лог.txt

[Izobara]

Сообщение от BDA

визуализация 12 теста
(красный - начало пути, голубой - конец)

Неплохо... Да, я бы с ней не справился. Надо браться за Окулова.

[Abstraction]

При максимуме длины пути в 200 шагов, не проще взять доску 400х400, отметить на ней "допустимые" квадраты и дальше натравить А*?