首页 > 代码库 > Snake Sequence

Snake Sequence

2024-08-03 13:05:57   217人阅读

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

Solution

 1 public int findSnakeSequence(int[][] matrix) { 2 //        List<List<Integer>> res = ArrayList<ArrayList<Integer>>(); 3     if(matrix == null || matrix.length == 0) { 4         return -1; 5     } 6     int m = matrix.length; 7     int n = matrix[0].length; 8      9     int[][] dp = new int[m][n];10     int globalMax = 0;11     12     //initialize13     dp[0][0] = 1;14     for(int i=1; i<n; i++) {15         if(Math.abs(matrix[0][i] - matrix[0][i-1]) == 1) 16             dp[0][i] = dp[0][i-1] + 1;17         else18             dp[0][i] = 1;19     }20     21     for(int i=1; i<m; i++) {22         if(Math.abs(matrix[i][0] - matrix[i-1][0]) == 1) 23             dp[i][0] = dp[i-1][0] + 1;24         else25             dp[i][0] = 1;26     }27     28     for(int i=1; i<m; i++) {29         for(int j=1; j<n; j++) {30             int max = 1;31             if(Math.abs(matrix[i][j] - matrix[i][j-1]) == 1)32                 max = dp[i][j-1] + 1;33             if(Math.abs(matrix[i][j] - matrix[i-1][j]) == 1)34                 max = Math.max(max, dp[i-1][j] + 1);35             dp[i][j] = max;36             globalMax = Math.max(max, globalMax);37         }38     }39     40     for (int i = 0; i < m; i++) {41     for (int j = 0; j < n; j++) {42         System.out.print(dp[i][j] + " ");43     }44     System.out.print("\n");45     }46     47     return globalMax;48         49 }

 

Snake Sequence


联系
我们