Skip to content

Instantly share code, notes, and snippets.

@congnt24

congnt24/gist:707c5830d719c52b454ba29a660b8b9d

Created June 10, 2019 05:18
Show Gist options
  • Save congnt24/707c5830d719c52b454ba29a660b8b9d to your computer and use it in GitHub Desktop.
Save congnt24/707c5830d719c52b454ba29a660b8b9d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. congnt24 created this gist Jun 10, 2019.
    89 changes: 89 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,89 @@
    let tmparr;
    // your code here
    function findMaxPathLength(map, row, col) {
    tmparr = new Array(row).fill(new Array(col).fill(-1));
    let max = 0;
    for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
    let x = recur(map, i, j);
    if (max < x) {
    max = x;
    }
    }
    }
    return max;
    }

    function recur(mat, x, y) {
    let point = 1, max = 0;
    let left = 999, top = 999, right = 999, down = 999;
    if (y > 0)
    left = mat[x][y - 1];
    if (x > 0)
    top = mat[x - 1][y];
    if (y < mat.length - 1)
    right = mat[x][y + 1];
    if (mat[0] && x < mat[0].length - 1)
    down = mat[x + 1][y];

    if (tmparr[x][y] > -1 || (mat[x][y] < left && mat[x][y] < right && mat[x][y] < top && mat[x][y] < down)) {
    return point;
    }
    if (left && mat[x][y] > left) {
    // let res = recur(mat, x, y - 1);
    let res = 1;
    if (tmparr[x][y-1] > -1) {
    res= tmparr[x][y-1];
    }else{
    res = recur(mat, x, y-1);
    }
    if (max < res) {
    max = res
    }
    }
    if (right && mat[x][y] > right) {
    // let res = recur(mat, x, y + 1);
    let res = 1;
    if (tmparr[x][y+1] > -1) {
    res= tmparr[x][y+1];
    }else{
    res = recur(mat, x, y+1);
    }
    if (max < res) {
    max = res
    }
    }

    if (top && mat[x][y] > top) {
    let res = 1;
    if (tmparr[x-1][y] > -1) {
    res= tmparr[x-1][y];
    }else{
    res = recur(mat, x - 1, y);
    }
    if (max < res) {
    max = res
    }
    }

    if (down && mat[x][y] > down) {
    let res = 1;
    if (tmparr[x+1][y] > -1) {
    res= tmparr[x+1][y];
    }else{
    res = recur(mat, x + 1, y);
    }
    if (max < res) {
    max = res
    }
    }
    tmparr[x][y] = point + max;
    return point + max;
    }


    function loadSmallDataset() {
    return [[4, 8, 7, 3], [2, 5, 9, 3], [6, 3, 2, 5], [4, 4, 1, 6]];
    }

    console.log(findMaxPathLength(loadSmallDataset(), 4, 4));