המבחן האחרון 2020א שאלות 1 ו 2

/**
 * The last Mavo test | 2020A
 */
public class LastTest {
    /**
     * Question 1
     */
    public static int minDiagSnake(int[][] mat) {
        if (mat.length <= 1)
            return 0;
        return minDiagSnakeHelper(mat, 0, 0, -1);
    }

    private static int minDiagSnakeHelper(int[][] mat, int i, int j, int prev) {
        int height = mat.length - 1;
        int width = mat[0].length - 1;
        int current, diff, count = -1, min = Integer.MAX_VALUE, topRight = Integer.MAX_VALUE, topLeft = Integer.MAX_VALUE, botRight = Integer.MAX_VALUE, botLeft = Integer.MAX_VALUE;

        //out of boundaries
        if (i < 0 || j < 0 || i > height || j > width)
            return -1;

        current = mat[i][j];
        diff = current > prev ? current - prev : prev - current;
        //if climb or jump were too high
        if (prev >= 0 && diff > 1)
            return -1;

        //if already visit
        if (current == -2)
            return -1;

        //if snake reached destination
        if (i == height && j == width)
            return 1;

        //go bottom right
        mat[i][j] = -2;
        count = minDiagSnakeHelper(mat, i + 1, j + 1, current);
        if (count != -1)
            botRight = 1 + count;
        mat[i][j] = current;

        //go bottom left
        mat[i][j] = -2;
        count = minDiagSnakeHelper(mat, i + 1, j - 1, current);
        if (count != -1)
            botLeft = 1 + count;
        mat[i][j] = current;

        //go top right
        mat[i][j] = -2;
        count = minDiagSnakeHelper(mat, i - 1, j + 1, current);
        if (count != -1)
            topRight = 1 + count;
        mat[i][j] = current;

        //go top left
        mat[i][j] = -2;
        count = minDiagSnakeHelper(mat, i - 1, j - 1, current);
        if (count != -1)
            topLeft += 1 + count;
        mat[i][j] = current;

        min = Math.min(Math.min(topRight, topLeft), Math.min(botRight, botLeft));
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    /**
     * Question 2
     */
    public static int minSumDeadEndSnake(int[][] mat) {
        if (mat.length <= 1)
            return 0;
        return minSumDeadEndSnakeHelper(mat, 0, 0, -1);
    }

    private static int minSumDeadEndSnakeHelper(int[][] mat, int i, int j, int prev) {
        int height = mat.length - 1;
        int width = mat[0].length - 1;
        int current, diff = 0, count = -1, min = Integer.MAX_VALUE, up = Integer.MAX_VALUE, left = Integer.MAX_VALUE, down = Integer.MAX_VALUE, right = Integer.MAX_VALUE;

        // i + 1 <= height && mat[i+1][j] != -2
        if(i < 0 || j < 0 || i > height || j > width)
            return -1;

        current = mat[i][j];
        if (prev != -1)
            diff = current > prev ? current - prev : prev - current;

        //if jump or climb are too high
        if (diff > 1)
            return -1;

        if(i == height && j == width)
            return current;

        //go down
        mat[i][j] = -2;
        count = minSumDeadEndSnakeHelper(mat, i + 1, j, current);
        down = count >= 0 ? count + current : down;
        mat[i][j] = current;

        //go left
        mat[i][j] = -2;
        count = minSumDeadEndSnakeHelper(mat, i, j - 1, current);
        left = count >= 0 ? count + current : left;
        mat[i][j] = current;
        //go up
        mat[i][j] = -2;
        count = minSumDeadEndSnakeHelper(mat, i - 1, j, current);
        up = count >= 0 ? count + current : up;
        mat[i][j] = current;

        //go right
        mat[i][j] = -2;
        count = minSumDeadEndSnakeHelper(mat, i, j + 1, current);
        right = count >= 0 ? count + current : right;
        mat[i][j] = current;

        min = Math.min(Math.min(up, down), Math.min(right, left));
        return min == Integer.MAX_VALUE ? current : min;
    }
}