## Monday, November 28, 2016

### Find longest Snake sequence in a given matrix | Algorithms

Find longest Snake sequence in a given matrix | Algorithms
Objective: Given two dimensional matrix, write an algorithm to find out the snake sequence which has the max­i­mum length. There could be many snake sequence in the matrix, you need to return the one with the max­i­mum length. Travel is allowed only in two directions, either go right OR go down.

What is snake sequence: Snake sequence can be made if number in adjacent right cell or number in the adjacent down cell is either +1 or –1 from the number in the current cell.

• This prob­lem is the exten­sion of the prob­lem “Count all paths from top left to bot­tom right of a mXn matrix” with some extra conditions.
• You can travel only in two direc­tions, either go right or go down.
• All we need to take care if one extra con­di­tion that we can travel only to the adja­cent cells (right or down) only if num­ber in those cells has dif­fer­ence of 1 from the cur­rent cell.
• Have a tem­po­rary stor­age , two dimen­sional array to store the results of snake result.
• Keep track­ing of max­i­mum length and at the end print the sequence using tem­po­rary array.
• We will use the Bottom-up approach of Dynamic pro­gram­ming and store the results of sub prob­lems to reuse them in future.
• See the recur­sive equa­tion and code for bet­ter understanding.

public int getMaxSequence(int [][] matrix){

int rows = matrix.length;
int cols = matrix[0].length;
int maxLenth =1;
int maxRow = 0;
int maxCol = 0;

//create result matrix
int [][] result = new int [rows][cols];

//if no sequence is found then every cell itself is a sequence of length 1
for (int i = 0; i <rows ; i++) {
for (int j = 0; j <cols ; j++) {
result[i][j] =1;
}
}

for (int i = 0; i <rows ; i++) {
for (int j = 0; j <cols ; j++) {
if(i!=0 || j!=0){
//check from left
if(i>0 && Math.abs(matrix[i][j]-matrix[i-1][j])==1){
result[i][j] = Math.max(result[i][j],
result[i-1][j]+1);
if(maxLenth<result[i][j]){
maxLenth = result[i][j];
maxRow = i;
maxCol = j;
}
}

//check from top
if(j>0 && Math.abs(matrix[i][j]-matrix[i][j-1])==1){
result[i][j] = Math.max(result[i][j],
result[i][j-1]+1);
if(maxLenth<result[i][j]){
maxLenth = result[i][j];
maxRow = i;
maxCol = j;
}
}
}
}
}

//Now we will check the max entry in the result[][].
System.out.println("Max Snake Sequence : " + maxLenth);
printPath(matrix, result, maxLenth, maxRow, maxCol);
return 0;
}

public void printPath(int [][] matrix, int [][] result, int maxLength, int maxRow, int maxCol){
int len =  maxLength;
while(maxLength>=1){
System.out.print(" - " + matrix[maxRow][maxCol]);
if(maxRow>0 && Math.abs(result[maxRow-1][maxCol]-result[maxRow][maxCol])==1){
maxRow--;
}else if(maxCol>0 && Math.abs(result[maxRow][maxCol-1]-result[maxRow][maxCol])==1){
maxCol--;
}
maxLength--;
}
}
Read full article from Find longest Snake sequence in a given matrix | Algorithms