Objective
Given a matrix, write an algorithm to find out the snake sequence which has the maximum length. There could be much snake sequence in the matrix; you need to return the one with the maximum length. Travel is allowed only in two directions; either go right OR goes down.
What is snake sequence?
Snake sequence can be made if number in an adjacent right cell or number in the adjacent down cell is either +1 or –1 from the number in the current cell.
Example
9
|
6
|
5
|
2
|
8
|
7
|
6
|
5
|
7
|
3
|
1
|
6
|
1
|
1
|
1
|
7
|
Approach
For each cell of the matrix, we keep the maximum length of a snake which ends in the current cell. The maximum length snake sequence will have the maximum value. The maximum value cell will correspond to the tail of the snake. In order to print the snake, we need to backtrack from tail all the way back to snake’s head. So avoid that backtracking, we will store the data solved subproblems(dynamic programming).
Solution: Dynamic Programming
Solution: Dynamic Programming
1. As we can travel only in two directions, either go right or go down. All we need to take care of the condition that we can travel only to the adjacent cells (right or down) only if the number of those cells has the difference of 1 from the current cell.
2. We will use dynamic programming for temporary storage, two-dimensional array to store the results of snake result.
3. Keep tracking of maximum length and at the end print the sequence using the temporary array.
4. We will use the Bottom-up approach of Dynamic programming and store the results of subproblems to reuse them in future.
Dynamic Programming relation is defined as
Let dp[i][i] represent maximum length of a snake which ends at cell (i, j).
Let dp[i][i] represent maximum length of a snake which ends at cell (i, j).
dp[i][j] = max(dp[i][j], dp[i][j – 1] + 1) if abs(matrix[i][j] - matrix[i][j – 1]) == 1
dp[i][j] = max(dp[i][j], dp[i – 1][j] + 1) if abs(matrix[i][j] - matrix[i – 1][j]) == 1
Snake problem code in Java:
package com.dp;
import java.util.Stack;
public class SnakeSequence {
/**
* This method will return the longest snake sequence.
* It works on the Dynamic programming concept.
* @param matrix
* @return longest snake sequence.
*/
private static void getLongestSnakeSeq(int[][] matrix, int row, int col) {
int[][] dp = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
dp[i][j] = 1;
}
}
int max_len = -1;
int idxI = -1; int idxJ = -1;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if(i>0 && Math.abs(matrix[i][j]-matrix[i-1][j])==1) {
dp[i][j] = Math.max(dp[i][j], dp[i-1][j]+1);
}
if(j>0 && Math.abs(matrix[i][j]-matrix[i][j-1])==1) {
dp[i][j] = Math.max(dp[i][j], dp[i][j-1]+1);
}
if(max_len<dp[i][j]) {
max_len = dp[i][j];
idxI = i;
idxJ = j;
}
}
}
System.out.println("Length of sequence "+max_len + "\nSequence is ");
printPath(matrix, dp, max_len, idxI, idxJ);
}
/**
* To print the snake path
*/
private static void printPath(int[][] matrix, int[][] dp, int maxLen,
int idxI, int idxJ) {
Stack<Integer> stack = new Stack<>();
while(maxLen >= 1) {
stack.add(matrix[idxI][idxJ]);
if(idxI>0 && Math.abs(dp[idxI-1][idxJ]-dp[idxI][idxJ])==1) {
idxI--;
} else if(idxJ>0 && Math.abs(dp[idxI][idxJ-1]-dp[idxI][idxJ])==1) {
idxJ--;
}
maxLen--;
}
/** To print the Sequence. */
for (Integer integer : stack) {
System.out.print(" " + integer);
}
}
/**
* Driver method.
* @param args
*/
public static void main(String[] args) {
int matrix[][] = {
{9, 6, 5, 2},
{8, 7, 6, 5},
{7, 3, 1, 6},
{1, 1, 1, 7}};
getLongestSnakeSeq(matrix, 4, 4);
}
}
Output:
Length of sequence 7
Sequence is
7 6 5 6 7 8 9
