Find maximum length Snake sequence - GeeksforGeeks
http://algorithms.tutorialhorizon.com/find-longest-snake-sequence-in-a-given-matrix/
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--;
}
}
http://www.techiedelight.com/maximum-length-snake-sequence/
Read full article from Find maximum length Snake sequence - GeeksforGeeks
Given a grid of numbers, find maximum length Snake sequence and print it. If multiple snake sequences exists with the maximum length, print any one of them.
A snake sequence is made up of adjacent numbers in the grid such that for each number, the number on the right or the number below it is +1 or -1 its value. For example, if you are at location (x, y) in the grid, you can either move right i.e. (x, y+1) if that number is ± 1 or move down i.e. (x+1, y) if that number is ± 1.
For example,
9, 6, 5, 2
8, 7, 6, 5
7, 3, 1, 6
1, 1, 1, 7
8, 7, 6, 5
7, 3, 1, 6
1, 1, 1, 7
In above grid, the longest snake sequence is: (9, 8, 7, 6, 5, 6, 7)
The idea is to use Dynamic Programming. For each cell of the matrix, we keep maximum length of a snake which ends in current cell. The maximum length snake sequence will have maximum value. The maximum value cell will correspond to tail of the snake. In order to print the snake, we need to backtrack from tail all the way back to snake’s head.
Let T[i][i] represent maximum length of a snake which ends at cell (i, j), then for given matrix M, the DP relation is defined as –
T[0][0] = 0
T[i][j] = max(T[i][j], T[i][j – 1] + 1) if M[i][j] = M[i][j – 1] ± 1
T[i][j] = max(T[i][j], T[i – 1][j] + 1) if M[i][j] = M[i – 1][j] ± 1
T[i][j] = max(T[i][j], T[i][j – 1] + 1) if M[i][j] = M[i][j – 1] ± 1
T[i][j] = max(T[i][j], T[i – 1][j] + 1) if M[i][j] = M[i – 1][j] ± 1
Time complexity of above solution is O(M*N). Auxiliary space used by above solution is O(M*N). If we are not required to print the snake, space can be further reduced to O(N) as we only uses the result from last row.
https://algorithms.tutorialhorizon.com/find-longest-snake-sequence-in-a-given-matrix/
http://www.algorithmforum.com/2017/09/find-longest-snake-sequence-in-given.html
http://www.algorithmforum.com/2017/09/find-longest-snake-sequence-in-given.html
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);
}
}
http://stackoverflow.com/questions/25095198/finding-snake-sequence-in-xy-graph-java// Function to find maximum length Snake sequence path// (i, j) corresponds to tail of the snakelist<Point> findPath(int grid[M][N], int mat[M][N], int i, int j){ list<Point> path; Point pt = {i, j}; path.push_front(pt); while (grid[i][j] != 0) { if (i > 0 && grid[i][j] - 1 == grid[i - 1][j]) { pt = {i - 1, j}; path.push_front(pt); i--; } else if (j > 0 && grid[i][j] - 1 == grid[i][j - 1]) { pt = {i, j - 1}; path.push_front(pt); j--; } } return path;}// Function to find maximum length Snake sequencevoid findSnakeSequence(int mat[M][N]){ // table to store results of subproblems int lookup[M][N]; // initialize by 0 memset(lookup, 0, sizeof lookup); // stores maximum length of Snake sequence int max_len = 0; // store cordinates to snake's tail int max_row = 0; int max_col = 0; // fill the table in bottom-up fashion for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // do except for (0, 0) cell if (i || j) { // look above if (i > 0 && abs(mat[i - 1][j] - mat[i][j]) == 1) { lookup[i][j] = max(lookup[i][j], lookup[i - 1][j] + 1); if (max_len < lookup[i][j]) { max_len = lookup[i][j]; max_row = i, max_col = j; } } // look left if (j > 0 && abs(mat[i][j - 1] - mat[i][j]) == 1) { lookup[i][j] = max(lookup[i][j], lookup[i][j - 1] + 1); if (max_len < lookup[i][j]) { max_len = lookup[i][j]; max_row = i, max_col = j; } } } } } cout << "Maximum length of Snake sequence is: " << max_len << endl; // find maximum length Snake sequence path list<Point> path = findPath(lookup, mat, max_row, max_col); cout << "Snake sequence is:"; for (auto it = path.begin(); it != path.end(); it++) cout << endl << mat[it->x][it->y] << " (" << it->x << ", " << it->y << ")" ;}http://algorithms.tutorialhorizon.com/find-longest-snake-sequence-in-a-given-matrix/
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--;
}
}
http://www.techiedelight.com/maximum-length-snake-sequence/
Read full article from Find maximum length Snake sequence - GeeksforGeeks
