CODEWITHSUNDEEP
javascriptalgorithmmatrixdata-structures
Karan Kumar
Karan Kumar

Reputation: 3176

Solving longest path in matrix

So this is the question to find longest path of 1s in a matrix of 0s and 1s from starting coordinates to the ending coordinates.

Here is the solution I figured out somehow and which I understand as well (almost). Though I am having trouble understanding one line of this:


function longestPath02(matrix, startPosition, endPosition) {
    let maxDistance = 0;
    const visited = {};

    function isValidCoordinate(i, j) {
        // check if the coordinates are in valid range
        // if (i < 0 || i > matrix.length - 1 || j > matrix[0].length - 1 || j < 0) return false;
        if (i > matrix.length - 1 || i < 0 || j > matrix[0].length - 1 || j < 0) return false;
        // check if the coordinate is one AND not visited
        if ((matrix[i] || [])[j] !== 1 || visited[`${i},${j}`]) return false;
        return true;
    }

    function calculate(startPosition, endPosition, distance) {
        const [i, j] = startPosition;
        const [x, y] = endPosition;

        if (i === x && j === y) {
            maxDistance = Math.max(distance, maxDistance);
            return;
        }

        visited[`${i},${j}`] = true;

        if (isValidCoordinate(i + 1, j)) calculate([i + 1, j], endPosition, distance + 1);
        if (isValidCoordinate(i - 1, j)) calculate([i - 1, j], endPosition, distance + 1);
        if (isValidCoordinate(i, j + 1)) calculate([i, j + 1], endPosition, distance + 1);
        if (isValidCoordinate(i, j - 1)) calculate([i, j - 1], endPosition, distance + 1);

        visited[`${i},${j}`] = false; // 👈
    }

    calculate(startPosition, endPosition, 0);
    return maxDistance;
}

Unable to understand why we have to set visited as false!

Without that, the result is incorrect. How is setting the coordinate visited as false relevant?

Dataset:

let mat = [
    [1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
    [1, 0, 1, 0, 1, 1, 1, 0, 1, 1],
    [1, 1, 1, 0, 1, 1, 0, 1, 0, 1],
    [0, 0, 0, 0, 1, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
    [1, 0, 0, 0, 1, 0, 0, 1, 0, 1],
    [1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
    [1, 1, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 1, 1, 0, 1, 0, 0],
];
console.log(longestPath02(mat, [0, 0], [5, 7]));

Upvotes: 0

Views: 356

Answers (1)

Leaderboard
Leaderboard

Reputation: 391

If I understand the code correctly, the highlighted line is backtracking.

Consider this line: visited[`${i},${j}`] = true;. The purpose of this line is to stop the recursive DFS from visiting a point you've just visited (otherwise you'll simply get a recursive loop).

But once that path is done with, you need to "reset", which is why you set it to false in the end. The reason is that otherwise, you're stopping future recursive calls from accessing that element! In other words, once you have finished going through one path, you need to free it so that another path can access that element if needed (otherwise that path will get confused and stop midway thinking that it has already accessed an element when it hasn't).

Upvotes: 2

Related Questions