[吐槽] Snake Sequence

Problem:

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

Thinking:

Use dynamic programming to find the possible maximum of snake sequence in the matrix. Then, use another method to get that snake sequence.

Java Code:

import java.util.ArrayList;
import java.util.List;

public class Snake {
    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);
        }
    }

    public static void main(String[] args) {
        int[][] matrix = { { 5, 3, 2, 4 }, { 4, 3, 1, -1 }, { 2, 1, 0, -1 },
                { 6, 0, 7, 0 } };
        findSnake(matrix);
    }
}

Reference:
http://www.1point3acres.com/bbs/thread-111959-1-1.html
http://www.careercup.com/question?id=14946605