Найти самый длинный путь в матрице с соседними буквами - PullRequest
Новая
       30

Найти самый длинный путь в матрице с соседними буквами

0 голосов
/ 04 декабря 2018

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

Например,если буква «E», вы можете перейти к «D» или «F».Вам разрешено двигаться вверх, вниз, влево, вправо, но только на одно место.Теперь я сделал аналогичную проблему с числами, где вы должны найти путь от верхнего левого угла до нижнего правого угла, и я предполагаю, что это будет аналогичная проблема с большим количеством ограничений.Это то, что у меня есть, я не уверен, как изменить это, чтобы сделать то, что мне нужно сделать для этой проблемы (есть препятствия, где он может пройти только через 0): 

def pathwithproblems(A):
    paths = [[0]*len(A[0] for i in A]
    if A[0][0] == 0:
        paths[0][0]=1
    for i in range(1, len(A)):
        if A[i][0] == 0:
            paths[i][0]=paths[i-1][0]
    for j in range(1, len(A)):
        if A[0][j] == 0:
            paths[0][j]=paths[0][j-1]
    for i in range(1, len(A)):
        for j in range(1, len(A)):
            if A[i][j] == 0:
                paths[i][j]=paths[i-1][j] + paths[i][j-1]
    return paths[-1][-1]

Для моей проблемы сбуквы, например, если матрица: 

L K M N O P Q R J
A B C D E F G H I

Мой ответ должен быть: 

JIHGFEDCBA

Если есть связь, я хочу вернуть тот, у которого самые низкие индексы строк и столбцови, если все еще есть связь, возвращение либо в порядке.Любая помощь будет принята с благодарностью!

Ответы [ 2 ]

0 голосов
/ 04 декабря 2018 
Another way to solve this problem is to have a helper function which will calculate all the lengths of the paths having adjacent letters and then the calling function can store only the longest one.

Псевдокод: 

helper(int[] mat, i, j, char c)
{
if i or j are outside the boundary conditions, return 0.
if difference between mat[i][j] and c is 1:
    return Math.max(
        helper(mat, i+1,j,mat[i][j]),
        helper(mat, i-1,j,mat[i][j]),
        helper(mat, i,j+1,mat[i][j]),
        helper(mat, i,j-1,mat[i][j]))+1;
else return 0;}
0 голосов
/ 04 декабря 2018

Это эквивалентно некоторому графику.Таким образом, первым шагом было бы определить граф 

ABE
DCZ

Стало бы 

A-B E
  |
D-C Z

Где теперь вы можете искать самый длинный путь (некоторые решения должны быть в Интернете)

...