Учитывая матрицу, состоящую из натуральных чисел, выведите путь с наименьшей суммой при обходе от верхнего левого элемента к нижнему правому. Вы можете двигаться вертикально, горизонтально и по диагонали. Обратите внимание, что можно перемещать вверх / вниз, вправо / влево и по диагонали во все стороны.

Пример:

 1*   9    7    3   10    2    2
10    4*   1*   1*   1*   7    8
 3    6    3    8    9    5*   7
 8   10    2    5    2    1*   4
 5    1    1    3    6    7    9*

Путь, дающий наименьшую сумму, отмечен звездочками и приводит к следующей сумме: 1 + 4 + 1 + 1 + 1 + 5 + 1 + 9 = 23 .

Тестовые случаи:

1   1   1
1   1   1
Output: 3

 7    9    6    6    4
 6    5    9    1    6
10    7   10    4    3
 4    2    2    3    7
 9    2    7    9    4
Output: 28

2  42   6   4   1
3  33   1   1   1
4  21   7  59   1
1   7   6  49   1
1   9   2  39   1
Output: 27 (2+3+4+7+7+1+1+1+1)

 5    6    7    4    4
12   12   25   25   25
 9    4   25    9    5
 7    4   25    1   12
 4    4    4    4    4
Output: 34 (5+12+4+4+4+1+4)

1   1   1   1
9   9   9   1
1   9   9   9
1   9   9   9
1   1   1   1
Output: 15

 2   55    5    3    1    1    4    1
 2   56    1   99   99   99   99    5
 3   57    5    2    2    2   99    1
 3   58    4    2    8    1   99    2
 4   65   66   67   68    3   99    3
 2    5    4    3    3    4   99    5
75   76   77   78   79   80   81    2
 5    4    5    1    1    3    3    2
Output: 67 (2+2+3+3+4+5+4+3+3+3+1+2+2+1+3+1+1+4+5+1+2+3+5+2+2)

Это код-гольф, поэтому выигрывает самый короткий код на каждом языке.

JavaScript, 442 412 408 358 байт

Это моя первая подача PPCG. Обратная связь будет оценена.

(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

Это принимает многомерный массив в качестве входных данных.

объяснение

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

демонстрация

f=(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

//Tests
console.log(f([[1,1,1],[1,1,1]])===3);
console.log(f([[7,9,6,6,4],[6,5,9,1,6],[10,7,10,4,3],[4,2,2,3,7],[9,2,7,9,4]])===28);
console.log(f([[2,42,6,4,1],[3,33,1,1,1],[4,21,7,59,1],[1,7,6,49,1],[1,9,2,39,1]])===27);
console.log(f([[5,6,7,4,4],[12,12,25,25,25],[9,4,25,9,5],[7,4,25,1,12],[4,4,4,4,4]])===34); 
console.log(f([[1,1,1,1],[9,9,9,1],[1,9,9,9],[1,9,9,9],[1,1,1,1]])===15)
console.log(f([[2,55,5,3,1,1,4,1],[2,56,1,99,99,99,99,5],[3,57,5,2,2,2,99,1],[3,58,4,2,8,1,99,2],[4,65,66,67,68,3,99,3],[2,5,4,3,3,4,99,5],[75,76,77,78,79,80,81,2],[5,4,5,1,1,3,3,2]])===67);

Редактировать: Отдельное спасибо @ETHproductions за помощь мне побрить десятки вкусных байтов.

Еще раз спасибо @Stewie Griffin за ваши советы, которые сбили 50 байтов.

Python 3 + NumPy + SciPy , 239 222 186 байт

from numpy import*
from scipy.sparse.csgraph import*
def f(M):m,n=s=M.shape;x,y=indices(s);return dijkstra([(M*(abs(i//n-x)<2)*(abs(i%n-y)<2)).flatten()for i in range(m*n)])[0,-1]+M[0,0]

Попробуйте онлайн!

Пакет обработки изображений Octave +, 175 162 157 151 142 139 байт

Сохранено 14 байтов благодаря @Luis Mendo и 1 байт благодаря @notjagan

function P(G)A=inf(z=size(G));A(1)=G(1);for k=G(:)'B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';B(5,:)-=G(:)';A=reshape(min(B),z);end,A(end)

Использует пакет обработки изображений, потому что почему бы и нет? Разве не так все решают проблемы с графами?

Попробуйте онлайн!

взорванный

function P(G)
   A=inf(z=size(G));         % Initialize distance array to all Inf
   A(1)=G(1);                % Make A(1) = cost of start cell
   for k=G(:)'               % For a really long time...
      B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';
       %  B=padarray(A,[1,1],inf);     % Add border of Inf around distance array
       %  B=im2col(B,[3,3]);           % Turn each 3x3 neighborhood into a column
       %  B=B+G(:)';                   % Add the weights to each row
      B(5,:)-=G(:)';         % Subtract the weights from center of neighborhood
      A=reshape(min(B),z);   % Take minimum columnwise and reshape to original
   end
   A(end)                    % Display cost of getting to last cell

объяснение

Дан массив весов:

7   12    6    2    4
5   13    3   11    1
4    7    2    9    3
4    2   12   13    4
9    2    7    9    4

Инициализируйте массив затрат, чтобы стоимость каждого элемента равнялась Бесконечности, за исключением начальной точки (левый верхний элемент), стоимость которой равна его весу.

  7   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Это итерация 0. Для каждой последующей итерации стоимость достижения ячейки устанавливается на минимум:

• текущая стоимость для достижения этого элемента, и
• текущая стоимость достижения соседей элемента + вес элемента

После первой итерации стоимость пути к элементу (2,2) (с использованием индексации на основе 1) будет

minimum([  7   Inf   Inf]   [13  13  13]) = 20
        [Inf   Inf   Inf] + [13   0  13]
        [Inf   Inf   Inf]   [13  13  13]

Полный массив затрат после первой итерации будет:

  7    19   Inf   Inf   Inf
 12    20   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

После итерации kкаждый элемент будет иметь наименьшую стоимость для достижения этого элемента с самого начала, принимая не более kшагов. Например, элемент в (3,3) может быть достигнут за 2 шага (итерации) по цене 22:

  7    19    25   Inf   Inf
 12    20    22   Inf   Inf
 16    19    22   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Но на 4-й итерации путь из 4 шагов найден со стоимостью 20:

 7   19   25   24   28
12   20   22   32   25
16   19   20   30   34
20   18   30   34   35
27   20   25   40   39

Поскольку ни один путь через матрицу mxn не может быть длиннее, чем количество элементов в матрице (как очень свободная верхняя граница), после m*nитераций каждый элемент будет содержать стоимость самого короткого пути для достижения этого элемента с самого начала.

JavaScript, 197 байт

a=>(v=a.map(x=>x.map(_=>1/0)),v[0][0]=a[0][0],q=[...(a+'')].map(_=>v=v.map((l,y)=>l.map((c,x)=>Math.min(c,...[...'012345678'].map(c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)))))),v.pop().pop())

приукрасить:

a=>(
  // v is a matrix holds minimal distance to the left top
  v=a.map(x=>x.map(_=>1/0)),
  v[0][0]=a[0][0],
  q=[
     // iterate more than width * height times to ensure the answer is correct
    ...(a+'')
  ].map(_=>
    v=v.map((l,y)=>
      l.map((c,x)=>
        // update each cell
        Math.min(c,...[...'012345678'].map(
          c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)
        ))
      )
    )
  ),
  // get result at right bottom
  v.pop().pop()
)

Mathematica 279 байт

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

FindShortestPathзатем используется, чтобы получить минимальный путь. Он работает EdgeWeight, а не VertexWeightтак, поэтому есть некоторый дополнительный код для определения EdgeWeightэлемента матрицы, соответствующего назначению каждого направленного ребра.

Код:

(m=Flatten[#];d=Dimensions@#;s=Range[Times@@d];e=Select[Tuples[s,2],0<ChessboardDistance@@(#/.Thread[s->({Ceiling[#/d[[1]]],Mod[#,d[[1]],1]}&/@s)])≤1&];Tr[FindShortestPath[Graph[s,#[[1]]->#[[2]]&/@e,EdgeWeight->(Last@#&/@Map[Extract[m,#]&,e,{2}])],1,Last@s]/.Thread[s->m]])&

Обратите внимание, что символ является символом транспонирования. Он будет вставлен в Mathematica как есть.

Использование:

%@{{2, 55, 5, 3, 1, 1, 4, 1},
  {2, 56, 1, 99, 99, 99, 99, 5},
  {3, 57, 5, 2, 2, 2, 99, 1},
  {3, 58, 4, 2, 8, 1, 99, 2},
  {4, 65, 66, 67, 68, 3, 99, 3},
  {2, 5, 4, 3, 3, 4, 99, 5},
  {75, 76, 77, 78, 79, 80, 81, 2},
  {5, 4, 5, 1, 1, 3, 3, 2}}

Выход:

67

Если вы установите, g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]а p=FindShortestPath[...затем следующий график будет визуально отображать решение (верхняя часть матрицы соответствует нижней части графика):

HighlightGraph[g,PathGraph[p,Thread[Most@p->Rest@p]]]

Haskell, 228 байт

Позиции - это списки из двух элементов, потому что их легко генерировать sequenceи сопоставлять по образцу с двумя кортежами.

h=g[[-1,-1]]
g t@(p:r)c|p==m=0|1<2=minimum$(sum$concat c):(\q@[a,b]->c!!a!!b+g(q:t)c)#(f(e$s$(\x->[0..x])#m)$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]])where m=[l(c)-1,l(head c)-1]
(#)=map
f=filter
e=flip elem
s=sequence
l=length

Начните с -1,-1и посчитайте стоимость каждого шага в поле назначения.

Альтернативно первые две строки: начинаются с 0,0, подсчитываются поля отправления, оканчиваются в координатах, равных размерам матрицы (так внизу справа от цели, которую необходимо добавить в список допустимых пунктов назначения) - точно такой же длины, но медленнее:

j=i[[0,0]]
i t@(p@[a,b]:r)c|p==m=0|1<2=c!!a!!b+(minimum$(sum$concat c):(\q->i(q:t)c)#(f(e$m:(s$(\x->[0..x-1])#m))$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]]))where m=[l c,l$head c]

Использование инфикса for mapне экономит здесь байты, но я заменяю его, как только он не стоит того, потому что он может стать лучше только при большем количестве применений, а иногда и при других реструктуризациях, которые сбрасывают другую пару скобок.

Быть улучшенным: избыточный filters. Слияние / в-выравнивая их filter(flip elem$(s$(\x->[0..x])#m)\\p)с import Data.Listна \\расходы 3 байта.

Кроме того, слишком плохо (fromEnumTo 0)на 2 байта больше, чем (\x->[0..x]).

sum$concat cсуммируется стоимость всех полей и, таким образом, кратко выражаемая верхняя граница стоимости пути, которая задается для того, minimumчтобы избежать пустого списка (моя программа проверки типов уже определила все, что нужно для работы с Integers, так что нет жесткого кодирования максимума Хе-хе). Независимо от того, как я ограничиваю шаги, основанные на предыдущем шаге (который сильно ускорил бы алгоритм, но также и на байтах), я не могу избежать тупиков, которые делают этот откат необходимым.

• Одна идея фильтра была ((not.e n).zipWith(-)(head r))с извлечением n=s[[-1..1],[-1..1]], которое требует добавления ,[-1,-1]к начальному пути. Затем алгоритм избегает перехода туда, куда он уже мог пойти на предыдущем шаге, что делает переход на граничное поле ортогонально этому краю тупиком.

• Другой был ((>=0).sum.z(*)d)с извлечением z=zipWith, которое вводит новый аргумент dв рекурсивную функцию, которая дается как (z(-)p q)в рекурсии, так и [1,1]в начальном случае. Алгоритм избегает последовательных шагов с отрицательным скалярным произведением ( dчто является предыдущим шагом), что означает отсутствие резких поворотов на 45 °. Это по-прежнему значительно сужает выбор и позволяет избежать предыдущего тривиального тупика, но все же есть пути, которые в конечном итоге будут заключены в уже посещенных полях (и, возможно, «побег», который, однако, будет резким поворотом).

Python 2, 356 320 байт

s=input()
r=lambda x:[x-1,x,x+1][-x-2:]
w=lambda z:[z+[(x,y)]for x in r(z[-1][0])for y in r(z[-1][1])if x<len(s)>0==((x,y)in z)<len(s[0])>y]
l=len(s)-1,len(s[0])-1
f=lambda x:all(l in y for y in x)and x or f([a for b in[l in z and[z]or w(z)for z in x]for a in b])
print min(sum(s[a][b]for(a,b)in x)for x in f([[(0,0)]]))

Попробуй это здесь!

-36 байт благодаря нотьягану !

Получает список списков в качестве входных данных и выводит наименьшую стоимость при перемещении по матрице сверху слева внизу справа.

объяснение

Найдите все возможные маршруты от верхнего левого до нижнего правого угла матрицы, создав список координат x, y для каждого маршрута. Маршруты не могут быть возвращены, и они должны заканчиваться в (len(s)-1,len(s[0])-1).

Суммируйте целые числа на каждом пути координат и возвращайте минимальную стоимость.

printМожет быть легко изменен , чтобы вывести список координат для кратчайшего маршрута.

APL (Dyalog Classic) , 33 байта

{⊃⌽,(⊢⌊⍵+(⍉3⌊/⊣/,⊢,⊢/)⍣2)⍣≡+\+⍀⍵}

Попробуйте онлайн!

{ } функция с аргументом ⍵

+\+⍀⍵ возьмите частичные суммы по строкам и столбцам, чтобы установить пессимистическую верхнюю границу расстояний пути

( )⍣≡ повторить до схождения:

• (⍉3⌊/⊣/,⊢,⊢/)⍣2Минимум расстояний до соседей, т.е. делайте дважды ( ( )⍣2): добавьте крайний левый столбец ( ⊣/,) к себе ( ⊢) и добавьте крайний правый столбец ( ,⊢/), найдите минимумы в горизонтальных тройках ( 3⌊/) и транспонируйте ( ⍉)

• ⍵+ добавить значение каждого узла к его минимуму расстояний до соседей

• ⊢⌊ попытаться превзойти текущие лучшие расстояния

⊃⌽, наконец, верните нижнюю правую ячейку