Тезею из лабиринта Минотавра помог выйти клубок ниток. Вы можете вместо клубка использовать персональный компьютер.
Написать программу, которая вводит маршрут Тезея в лабиринте и находит обратный путь, по которому Тезей сможет выйти из лабиринта, не заходя в тупики и не делая петель.
Входные данные: Входные данные содержит маршрут Тезея, который представлен строкой, состоящей из букв: N, S, W, E и длиной не более 200.
Буквы означают:
N - один "шаг" на север, вврех
S - один "шаг" на юг, вниз
W - один "шаг" на запад, лево
E - один "шаг" на восток. право
Выходные данные: В выходные данные записывается аналогично входным данным обратный путь.
Формат ввода
EENNESWSSWE
Формат вывода
NWW
Другие языки программирования и технологии
написать программу на Pascal.
const
N = 1 shl 8;
E = 2 shl 8;
S = 4 shl 8;
W = 8 shl 8;
type
arr = array [-200 .. 200, -200 .. 200] of integer;
tpoint = record
x, y, lvl: integer;
end;
var
a: arr;
i, j, k: integer;
c: char;
procedure search(var a: arr; x, y: integer);
const
count = 20;
var
p: array [0 .. count - 1] of tpoint;
cur, fr: integer;
begin
cur := 0;
fr := 1;
p[cur].x := x;
p[cur].y := y;
p[cur].lvl := 1;
while cur <> fr do
begin
if a[p[cur].y, p[cur].x] and 255 <> 0 then
begin
cur := (cur + 1) mod count;
continue;
end;
a[p[cur].y, p[cur].x] := a[p[cur].y, p[cur].x] or p[cur].lvl;
if a[p[cur].y, p[cur].x] and N > 0 then
begin
p[fr].y := p[cur].y + 1;
p[fr].x := p[cur].x;
p[fr].lvl := p[cur].lvl + 1;
fr := (fr + 1) mod count;
end;
if a[p[cur].y, p[cur].x] and S > 0 then
begin
p[fr].y := p[cur].y - 1;
p[fr].x := p[cur].x;
p[fr].lvl := p[cur].lvl + 1;
fr := (fr + 1) mod count;
end;
if a[p[cur].y, p[cur].x] and E > 0 then
begin
p[fr].y := p[cur].y;
p[fr].x := p[cur].x + 1;
p[fr].lvl := p[cur].lvl + 1;
fr := (fr + 1) mod count;
end;
if a[p[cur].y, p[cur].x] and W > 0 then
begin
p[fr].y := p[cur].y;
p[fr].x := p[cur].x - 1;
p[fr].lvl := p[cur].lvl + 1;
fr := (fr + 1) mod count;
end;
cur := (cur + 1) mod count;
end;
end;
function printpath(const a: arr; x, y: integer): boolean;
var
lvl: integer;
begin
lvl := a[y, x] and 255;
if lvl = 1 then
begin
printpath := True;
exit;
end;
if (a[y, x] and S > 0) and (a[y - 1, x] and 255 = lvl - 1) and printpath(a,
x, y - 1) then
begin
write('N');
printpath := True;
exit;
end;
if (a[y, x] and W > 0) and (a[y, x - 1] and 255 = lvl - 1) and printpath(a,
x - 1, y) then
begin
write('E');
printpath := True;
exit;
end;
if (a[y, x] and N > 0) and (a[y + 1, x] and 255 = lvl - 1) and printpath(a,
x, y + 1) then
begin
write('S');
printpath := True;
exit;
end;
if (a[y, x] and E > 0) and (a[y, x + 1] and 255 = lvl - 1) and printpath(a,
x + 1, y) then
begin
write('W');
printpath := True;
exit;
end;
printpath := false;
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;
search(a, j, i);
printpath(a, 0, 0);
end.
N = 1 shl 8;
E = 2 shl 8;
S = 4 shl 8;
W = 8 shl 8;
type
arr = array [-200 .. 200, -200 .. 200] of integer;
tpoint = record
x, y, lvl: integer;
end;
var
a: arr;
i, j, k: integer;
c: char;
procedure search(var a: arr; x, y: integer);
const
count = 20;
var
p: array [0 .. count - 1] of tpoint;
cur, fr: integer;
begin
cur := 0;
fr := 1;
p[cur].x := x;
p[cur].y := y;
p[cur].lvl := 1;
while cur <> fr do
begin
if a[p[cur].y, p[cur].x] and 255 <> 0 then
begin
cur := (cur + 1) mod count;
continue;
end;
a[p[cur].y, p[cur].x] := a[p[cur].y, p[cur].x] or p[cur].lvl;
if a[p[cur].y, p[cur].x] and N > 0 then
begin
p[fr].y := p[cur].y + 1;
p[fr].x := p[cur].x;
p[fr].lvl := p[cur].lvl + 1;
fr := (fr + 1) mod count;
end;
if a[p[cur].y, p[cur].x] and S > 0 then
begin
p[fr].y := p[cur].y - 1;
p[fr].x := p[cur].x;
p[fr].lvl := p[cur].lvl + 1;
fr := (fr + 1) mod count;
end;
if a[p[cur].y, p[cur].x] and E > 0 then
begin
p[fr].y := p[cur].y;
p[fr].x := p[cur].x + 1;
p[fr].lvl := p[cur].lvl + 1;
fr := (fr + 1) mod count;
end;
if a[p[cur].y, p[cur].x] and W > 0 then
begin
p[fr].y := p[cur].y;
p[fr].x := p[cur].x - 1;
p[fr].lvl := p[cur].lvl + 1;
fr := (fr + 1) mod count;
end;
cur := (cur + 1) mod count;
end;
end;
function printpath(const a: arr; x, y: integer): boolean;
var
lvl: integer;
begin
lvl := a[y, x] and 255;
if lvl = 1 then
begin
printpath := True;
exit;
end;
if (a[y, x] and S > 0) and (a[y - 1, x] and 255 = lvl - 1) and printpath(a,
x, y - 1) then
begin
write('N');
printpath := True;
exit;
end;
if (a[y, x] and W > 0) and (a[y, x - 1] and 255 = lvl - 1) and printpath(a,
x - 1, y) then
begin
write('E');
printpath := True;
exit;
end;
if (a[y, x] and N > 0) and (a[y + 1, x] and 255 = lvl - 1) and printpath(a,
x, y + 1) then
begin
write('S');
printpath := True;
exit;
end;
if (a[y, x] and E > 0) and (a[y, x + 1] and 255 = lvl - 1) and printpath(a,
x + 1, y) then
begin
write('W');
printpath := True;
exit;
end;
printpath := false;
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;
search(a, j, i);
printpath(a, 0, 0);
end.
Просто строку разверни, сдайте задачу и удали Паскаль, отформатируй жесткий диск. В идеале купи новый комп и Сотри у себя память об этом языке
Похожие вопросы
- Напишите программу на Pascal. В цистерне N литров молока.
- Люди помогите написать программы для Pascal очень срочно и очень нужно
- Помогите ламеру написать программу на Pascal.
- Помогите написать программу в PASCAL!!!
- нужно написать программу в Pascal.
- Помогите написать программу в Pascal abc net
- Помогите написать программы по Pascal ABC
- Помогите написать программу на pascal'е
- Помогите написать программу на Pascal Срочно
- Помогите Написать программу (на Pascal) для решения квадратного уравнения.