CODEWITHSUNDEEP
pythonpython-3.xmatrixdata-structuresdynamic-programming
mlenthusiast
mlenthusiast

Reputation: 1194

Find longest path in matrix with adjacent letters

I'm trying to write a program that will show the longest path given a matrix of any size, which moves from letter to letter, but can only move to an adjacent letter.

For ex. if you letter is 'E', you can move to 'D' or 'F'. You are allowed to move up, down, left, right, but only one spot. Now I have done a similar problem with numbers, where you have to find a path from top left corner to bottom right corner, and I am assuming it would be a similar problem with more constraints. This is what I have, I'm not sure how to modify this to do what I need to do for this problem(has obstacles where it can only go through 0's):

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]

For my problem with letters, for example if a matrix is:

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

My answer should be:

JIHGFEDCBA

If there is a tie, I want to return the one with lowest row and column indices, and if there still is a tie, returning either is fine. Any help would be really appreciated!

Upvotes: 0

Views: 704

Answers (2)

Rishab Ghanti
Rishab Ghanti

Reputation: 46

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.

Pseudo code:

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;}

Upvotes: 1

sehigle
sehigle

Reputation: 332

This is equivalent to some graph. So the first step would be to dermine the graph 

ABE
DCZ

Would become

A-B E
  |
D-C Z

Where you can now search for the longest path (some solutions should be on the internet)

Upvotes: 0

Related Questions