You are given a grid of numbers. A snake sequence is made up of adjacent numbers such that for each number, the number on the right or the number below it is +1 or -1 its value. For example,
1 3 2 6 8
-9 7 1 -1 2
1 5 0 1 9
In this grid, (3, 2, 1, 0, 1) is a snake sequence.
Given a grid, find the longest snake sequences and their lengths (so there can be multiple snake sequences with the maximum length).
http://blog.csdn.net/sammylan/article/details/39520839
昨天朋友问我这样一道面试题,第一感觉是用DFS,后来想了一下其实用DP效率跟高,以下是DP方程(相连是指亮点之间可以走动)
/*
F(i,j) = 1 + max(f(i-1,j),f(i,j-1)) 如果P(i,j) 跟P(i-1,j),P(i,j-1)都相连
= 1 + f(i-1,j) 如果P(i,j)跟P(i-1,j)相连
= 1 + f(i,j - 1) 如果P(i,j) 跟P(i,j-1)都相连
= 1 如果P(i,j) 跟P(i-1,j),P(i,j-1)都不相连
*/
http://codechen.blogspot.com/2015/08/snake-sequence.html
Use dynamic programming to find the possible maximum of snake sequence in the matrix. Then, use another method to get that snake sequence.
public static void findSnake(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
int[][] dp = new int[matrix.length][matrix[0].length];
int max = findMax(matrix, dp);
List<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (dp[i][j] == max) {
backtrack(matrix, dp, i, j, result, new ArrayList<String>());
}
}
}
for (List<String> list : result) {
for (String s : list) {
System.out.println(s);
}
System.out.println();
}
}
public static int findMax(int[][] matrix, int[][] dp) {
int max = 1;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
dp[i][j] = 1;
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (i > 0 && Math.abs(matrix[i - 1][j] - matrix[i][j]) == 1) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + 1);
}
if (j > 0 && Math.abs(matrix[i][j - 1] - matrix[i][j]) == 1) {
dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + 1);
}
max = Math.max(max, dp[i][j]);
}
}
return max;
}
public static void backtrack(int[][] matrix, int[][] dp, int i, int j,
List<ArrayList<String>> result, List<String> path) {
if (dp[i][j] == 1) {
path.add("matrix[" + i + "][" + j + "]: " + matrix[i][j]);
result.add(new ArrayList<String>(path));
return;
}
if (i > 0 && dp[i - 1][j] == dp[i][j] - 1
&& Math.abs(matrix[i - 1][j] - matrix[i][j]) == 1) {
path.add("matrix[" + i + "][" + j + "]: " + matrix[i][j]);
backtrack(matrix, dp, i - 1, j, result, path);
path.remove(path.size() - 1);
}
if (j > 0 && dp[i][j - 1] == dp[i][j] - 1
&& Math.abs(matrix[i][j - 1] - matrix[i][j]) == 1) {
path.add("matrix[" + i + "][" + j + "]: " + matrix[i][j]);
backtrack(matrix, dp, i, j - 1, result, path);
path.remove(path.size() - 1);
}
}