Герои

Данная задача сводится к классическому волновому алгоритму поиска наикратчайшего пути в неориентированном невзвешенном графе, данный алгоритм также называют поиском в ширину. Здесь вершинами служат прямоугольные участки дворцовского сада, а ребра соединяют смежные участки, т.е. участки имеющие общую сторону. Данный алгоритм необходимо применить для каждого из мушкетеров и найти длину наикратчайшего пути от него до королевы, далее следует сложить количество подвесок тех мушкетеров, для которых длина пути не превышает L, полученное значение и будет ответом на задачу.

Рассмотрим более детально использование волнового алгоритма при решении данной задачи. В силу небольших ограничений на N и M можно не использовать очередь при обходе графа, которая дает алгоритм сложностью порядка O(N*M), а ограничиться более жадным алгоритмом со сложностью O(N²*M²). Введем следующие обозначения:

(x,y) – координата текущего мушкетера,

(qx,qy) – координата королевы

a[i][j] – массив, содержащий карту сада, заданную во входных данных,

b[i][j] – массив, содержащий количество клеток в наикратчайшем маршруте от клетки (x,y) до текущей клетки (i,j).

Первоначально обнулим массив b и выполним присвоение b[x][y]=1. Будем считать, что если элемент данного массива равен нулю, то оптимальный маршрут еще не известен, в начале алгоритма нам будут известны только те клетки, в которые возможно попасть за 0 шагов, т.е. речь идет о единственной клетке (x,y). Далее, будем осуществлять обход и искать все клетки массива b с нулевыми значениями, у которых соседом является клетка со значением 1, при обнаружении будем заносить в них значение 2, таким образом, мы определим все клетки, в которые можно попасть за один шаг, далее поставим значение 3 в нулевые клетки, смежные с клетками со значением 2 и т.д., на k-м шаге мы будем рассматривать нулевые клетки, смежные с клетками со значением k и ставить в них число k+1. Очевидно, что если маршрут в некоторую клетку существует, то количество шагов при оптимальном движении не может превышать M*N, поэтому достаточно выполнить M*N таких шагов. В результате в b[qx][qy] мы получим значение, на единицу превышающее длину оптимального маршрута из (x,y) в (qx,qy), если такой маршрут существует, и значение 0 в противном случае. Используя значение b[qx][qy], не сложно определить: успевает ли текущий мушкетер добраться до королевы в отведенное время.

Алгоритмическая реализация вышеописанного:

  int d[1..8]=(1,0,0,1,-1,0,0,-1)

  readln(n,m)
  for i=1..n readln(a[i])
  read(qx,qy,l)

  s=0
  for t=1..4{
    b={0,…,0}
    read(x,y,p)
    b[x][y]=1
    for k=1..n*m
      for i=1..n
        for j=1..m
          if(a[i][j]='0' and b[i][j]=0)
            for r=1..4{
              x=i+d[2*r-1]; y=j+d[2*r]
              if(b[x][y]=k) b[i][j]=k+1
            }
    if(b[qx][qy] > 0 and b[qx][qy] < l+2) s=s+p
  }

  write(s)

Стоит обратить внимание на то, что все координаты заданы нестандартным образом, а именно ось абсцисс OX направлена вдоль строк, а ось ординат OY – вдоль столбцов. Приведенные примеры имеют квадратные симметричные поля, по которым этого не видно. Таким образом, невнимательное прочтение формата входных данных может привести к ошибочной реализации.

[Обсуждение] [Все попытки] [Задача]