7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2010

Подразделы

Другие разделы

Дата и время

27/04/2024 22:58:22

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printРазбор задачи K. Очистка озера

Тема: поиск в ширину
Сложность: средняя

С помощью поиска в ширину находим минимальное число ходов от клетки с подъемником и от начальной клетки с роботом. Для поиска в ширину используется очередь.
var q:array[1..10000] of record i,j:integer; end;
  dist:array[1..2,1..100,1..100] of integer;
  map:array[1..100] of string;
  q1,q2,n,m,r,c,d,e:longint;
{ выполнение хода в клетку (r,c), её достигли за di шагов из начальной позиции }
procedure move2(d,r,c,di:integer);
begin
  if (r<1) or (r>n) or (c<1) or (c>m) then {нельзя} exit;
  if map[r][c]='#' then {нельзя} exit;
  if dist[d,r,c]>=0 then {уже были} exit;
  dist[d,r,c]:=di;
  { добавляем в очередь }
  q[q2].i:=r;
  q[q2].j:=c;
  inc(q2);
end;
procedure flood(r,c,d:integer);
var i,j,di:integer;
begin
  for i:=1 to n do
    for j:=1 to m do
      dist[d,i,j]:=-1; { отмечаем, что не были }
  q1:=1; { очередь пуста }
  q2:=1;
  move2(d,r,c,0); { помещаем в очередь стартовую позицию }
  while q1<q2 do { очередь не пуста }
  begin
    { берем первое значение из очереди }
    i:=q[q1].i;
    j:=q[q1].j;
    inc(q1);
    di:=dist[d,i,j]+1;
    { ходим во всех возможных направлениях }
    move2(d,i+1,j,di);
    move2(d,i-1,j,di);
    move2(d,i,j+1,di);
    move2(d,i,j-1,di);
  end;
end;
...
  flood(d,e,1);
  flood(r,c,2);
Теперь нужно проверить два особых случая:
  • робот не может дойти до подъемника (т.е. `"dist"[1,r,c]\ <\ 0`);
  • все клетки, в которые может попасть робот, пусты, кроме клетки с подъемником.
В обоих случаях робот может не работать, выводим количество единиц мусора в клетке с подъемником и время 0.
В остальных случаях робот всегда должен носить мусор по одной единице в клетку с подъемником. Варианты с выбрасыванием мусора по пути, чтобы взять другой, не дают экономии времени, так как придется вернуться за выброшенным мусором. Поэтому все единицы мусора, кроме самой первой, робот собирает, отправляясь за ними из клетки с подъемником и затем возвращаясь в нее обратно по своим следам. Т.е. почти на каждую единицу мусора робот тратит `2*"dist"[1,i,j]` единиц времени, где `"dist"[1,i,j]` – количество ходов от клетки с подъемником до клетки `(i,j)`. Экономия времени может быть только за счет правильного выбора первой собираемой единицы мусора. При собирании первой единицы мусора робот проходит до нее `"dist"[2,i,j]` ходов вместо `"dist"[1,i,j]`, где `"dist"[2,i,j]` – количество ходов от начальной позиции робота до клетки `(i,j)`.
Таким образом минимальное время равно:
`sum_{AA\ i\ j\ :\ "dist"[1,i,j]≥0}\ 2*"map"[i][j]*"dist"[1,i,j]\ +\ min_{AA\ i\ j\ :\ "map"[i][j]≠'0'\ ^^\ "dist"[1,i,j]>0}\ ("dist"[2,i,j]-"dist"[1,i,j])`
loading