Friday, July 03, 2020

calc grid min given directions

Calculate min for a grid starting from top row and going down in 3 directions (down-left, down, down-right).
00 01 02 -> j
10 11 12
20 21 22
calcMin(grid):
    if grid == null
        || grid.length() == 0
        || grid[0].length() == 0:
        throw
    rows = grid.length()
    cols = grid[0].length()
    mins = new [rows, cols]
    calcMins(grid, rows, cols, mins)
    min = getMin(mins, cols)
    return min

calcMins(grid, rows, cols, mins):
    for i = 0, i < rows, i++:
        calcMin(grid, rows, cols, i, 0, mins)

calcMin(grid, rows, cols, i, j, mins):
    if !(0 <= i < rows):
        return null
    if !(0 <= j < cols):
        return null
    if mins[i][j] != null:
        return mins[i][j]
    min =
        checked(
            grid[i][j]
                + min(
                    calcMin(grid, rows, cols, i+1, j-1], mins),
                    calcMin(grid, rows, cols, i+1,   j], mins),
                    calcMin(grid, rows, cols, i+1, j+1], mins)
                    )
            )
    mins[i][j] = min
    return min

min(a, b, c):
    if a == null && b == null && c == null:
        return 0
    return
        math.min(
            a ?? int.max,
            b ?? int.max,
            c ?? int.max
            )

getMin(mins, cols):
    min = mins[0][0]
    for j = 1, j < cols, j++:
        min = math.min(min, mins[0][j])
    return min
[Hat tip to SM]

No comments:

Post a Comment