首页 > 代码库 > Snake Sequence

Snake Sequence

2024-07-26 03:56:47   221人阅读

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

output : 3 2 1 0 1

1. Given a grid, find the longest snake sequences and their lengths (so there can be multiple snake sequences with the maximum length).

public class Solution {    public List<List<Integer>> SnakeSequence(int[][] grid) {        List<List<Integer>> ret = new LinkedList<List<Integer>>();        int m = grid.length;        int n = grid[0].length;        int[][] dp = new int[m][n];        int longest = 0;        for(int i=0; i<m; i++) {            for(int j=0; j<n; j++) {                if(i>0 && Math.abs(grid[i-1][j]-grid[i][j])==1) {                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j]+1);                }                if(j>0 && Math.abs(grid[i][j-1]-grid[i][j])==1) {                    dp[i][j] = Math.max(dp[i][j], dp[i][j-1]+1);                }                if(dp[i][j]>longest) {                    longest = dp[i][j];                }            }        }        }

 

2. What about the longest increasing(by +1) snake sequence. This time, the numbers are in an increasing order in the sequence.

For example
2 3 4 5
4 5 10 11
20 6 9 12
6 7 8 40

output : 4 5 6 7 8 9 10 11 12

////  main.cpp//  TestC_cpp////  Created by Joyce on 14-10-8.//  Copyright (c) 2014年 Yang Li. All rights reserved.//#include <iostream>using namespace std;int arr[4][4] = {{2,3,4,5},{4,5,10,11},{20,6,9,12},{6,7,8,40}}; // given array.int temp[4][4];int M=4, N=4;int fill(int temp[][4], int i, int j){    if(i<0 || j<0 || i>=M || j>=N)        return 0;        if(temp[i][j] != 0)        return temp[i][j];        int left=0,right=0,up=0,down=0;    if(arr[i-1][j] == arr[i][j] +1){ /// cpp compiler won‘t claim if the idx is over limit        up = fill(temp,i-1,j);        if(up+1>temp[i][j])            temp[i][j] = up+1;    }    if(arr[i+1][j] == arr[i][j] +1) {        down = fill(temp,i+1,j);        if(down+1>temp[i][j])            temp[i][j] = down+1;    }    if(arr[i][j-1] == arr[i][j] +1){        left = fill(temp,i,j-1);        if(left+1>temp[i][j])            temp[i][j] = left+1;    }    if(arr[i][j+1] == arr[i][j] +1){        right = fill(temp,i,j+1);        if(right+1>temp[i][j])            temp[i][j] = right+1;    }    return temp[i][j];}int main(int arg, char** args) {    int i, j;    for (i=0;i<M;i++){        for(j=0;j<N;j++){            if(temp[i][j] == 0){                fill(temp,i,j);            }        }    }    for(i=0; i<4; i++) {        for(j=0; j<4; j++) {            cout<<temp[i][j];        }        cout<<‘\n‘;    }    // find the max elem in temp    int max_x=0, max_y=0;    for(i=0;i<M;i++){        for(j=0;j<N;j++){            if(temp[i][j] > temp[max_x][max_y]){                max_x = i;                max_y = j;             }         }     }    // find the path    i=max_x, j= max_y ;    cout<<arr[i][j]<<‘,‘;    while(temp[i][j] != 0){        if(temp[i-1][j] == temp[i][j]-1 && arr[i-1][j] == arr[i][j]+1){            i = i-1;            cout<<arr[i][j]<<‘,‘;            continue;        }        if(temp[i+1][j] == temp[i][j]-1 && arr[i+1][j] == arr[i][j]+1){            i = i+1;            cout<<arr[i][j]<<‘,‘;            continue;        }        if(temp[i][j-1] == temp[i][j]-1 && arr[i][j-1] == arr[i][j]+1){            j = j-1;            cout<<arr[i][j]<<‘,‘;            continue;         }         if(temp[i][j+1] == temp[i][j]-1 && arr[i][j+1] == arr[i][j]+1){            j = j+1;             cout<<arr[i][j]<<‘,‘;            continue;         }     } }

 

Snake Sequence


联系
我们