Saturday, August 22, 2015

Find length of the longest consecutive path from a given starting character

Given a matrix of characters. Find length of the longest path from a given character, such that all characters in the path are consecutive to each other, i.e., every character in path is next to previous in alphabetical order. It is allowed to move in all 8 directions from a cell.

example:

for mat[][]={{a,c,d},
                     {h,b,e},
                     {i,g,f}} 
and input character 'e' o/p will be 5

At first this problem is looking easy (Indeed this is) by simply finding the next character via doing a 8 way recursion, this is doable this way but we can do it more efficiently by using dynamic programing, there can be some subproblem while we are searching for a path so we will store that paths in our dp matrix and will use it in between.

simple solution in java 

class SearchPath
{
    public static final int R=3;
    public static final int C=3;

    // matrix for tracking purpose 
    public static boolean [][] visited;
    
    //input matrix
    public static char [][] mat ={ {'a','c','d'},{ 'h','b','a'},{ 'i','g','f'}};
    
    // just storing all 8 position for iterative recurs 
    public static int [] x = {1,0,1,1,-1,-1,0,-1};
    public static int [] y = {0,1,1,-1,1,-1,-1,0};
    
    //dp storage
    public static int [][]dp;
    
    public static int max(int a, int b)
    {
        return(a>b?a:b);
    } 

    //will check if and i,j pair in matrix valid or not
    public static boolean isValid(int i, int j)
    {
        if(i<0 || j<0 || i>=R || j >=C)
            return false;
        else
            return true;
    }
    
    public static int getpath_util(char m, int r, int c)
    {
        if(!isValid(r,c) || visited[r][c] ||  m+1 != mat[r][c])
            return 0;
        if(dp[r][c]!= -1)
        {
            return dp[r][c];
        }
        
        // make this visited so in subsequent call it will not be taken into account
        
        visited[r][c] = true;
        int ans=0;
        for(int k=0; k<8; k++)
        {
            ans= max(ans, 1+getpath_util(mat[r][c], x[k]+r, y[k]+c));
        }  
        
        // unset this
        visited [r][c] = false;
        
        return dp[r][c] = ans;
        
    }
    public static void getpath(char m)
    {
        int ans=0;
        for(int i=0; i<R; i++)
        {
            for(int k=0; k<C;k++)
            {
                if(mat[i][k] == m)
                {
                    for(int j=0; j<8; j++)
                    {   
                        ans = max(ans, 1+getpath_util(m, i+x[j], k+y[j]));
                    }       
                }
            }
        }   
        System.out.println(ans);
    }
    public static void main(String[]args)
    { 
        visited  = new boolean[R][C];
        dp = new int [R][C];
        for(int i=0; i<R;i++)
            for(int k=0; k<C; k++)
                dp[i][k]=-1;
        for(int i=0; i<R;i++)
            for(int k=0; k<C; k++)
                visited[i][k]=false;
        getpath('a');
        getpath('e');
        getpath('b');
        getpath('f'); 
    }

}


Source:- gfg

No comments:

Post a Comment