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