Задание. Исполнитель робот перемещается по квадратному полю размером 50 на 50 клеток. Робот может выполнить следующие действия:
- сделать шаг влево на одну клетку;
- сделать шаг вправо на одну клетку;
- сделать шаг вверх на одну клетку;
- закрасить клетку.
Изначально
робот находится в клетке с координатами (1;1). Необходимо написать
программу, определяющую за какое минимальное число шагов робот закрасит
заданные клетки. Число и координаты закрашиваемых клеток вводятся из
файла Robot.in, результат записывается в файл Robot.out.
robot.in
| robot.out
| 4
1 1
10 2
1 3
10 4
| 30
| 1
1 1
| 0
|
Решение:
Алгоритм решения задачи:
1) чтение данных из файла, задание начальных значений;
2) проверяем есть ли не закрашенные клетки - если клеток нет переходим к п.7;
3)находим наименьшее y в котором есть клетка для закраски и перемещаемся роботом вертикально до y;
4)
для данного у находим минимальный и максимальный х, соответствующие
клеткам которые необходимо закрасить. Если в данной строке клетка для
закрашивания одна, то максимальный и минимальный х совпадут.
5)
находим наименьшее расстояние от текущей клетки до крайней левой и
правой, закрашиваемой клетки, в данной строке. Идем сначала до ближайшей
клетки, потом идем к дальней;
6) переходим к п 2;
7) вывод результата
Запись на языке программирования:
program robot;
var xmin,xmax,ymin:integer;
x,y,h,i,k,n:integer;
kx,ky:array[1..50] of integer;
ft:text;
BEGIN
Assign(ft,'Robot.in');
Reset(ft);
Readln(ft,n);
for i:=1 to n do
begin
Read(ft,kx[i]);
Readln(ft,ky[i]);
end;
close(ft);
x:=1;y:=0;ymin:=50;h:=-1;k:=0;
while k<n do
begin
ymin:=50;
for i:=1 to n do if (ky[i]<ymin) and (ky[i]>y) then ymin:=ky[i];
h:=h+abs(y-ymin);
y:=ymin;
xmin:=50;xmax:=1;
for i:=1 to n do
if ky[i]=y then
begin
k:=k+1;
if kx[i]<=xmin then xmin:=kx[i];
if kx[i]>=xmax then xmax:=kx[i];
end;
if xmin=xmax then
begin
h:=h+abs(xmin-x);
x:=xmin;
end
else
if abs(xmin-x)>abs(xmax-x) then
begin
h:=h+abs(xmin-x)+2*abs(xmax-x);
x:=xmin;
end
else
begin
h:=h+abs(xmax-x)+2*abs(xmin-x);
x:=xmax;
end;
end;
writeln('h=',h);
Assign(ft,'Robot.out');
Rewrite(ft);
writeln(ft,h);
close(ft);
END.
| 
