Home > OS >  Solving longest path in matrix
Solving longest path in matrix

Time:07-04

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; //            
  • Related