Skip to main content

Longest possible route in a matrix with hurdles

Finding the longest possible route in a matrix from a given source cell to a destination cell, while considering the presence of hurdles in the matrix. The goal is to determine the maximum number of steps one can take while moving only in up, down, left, or right directions, and avoiding the hurdles.

Problem Statement and Description

Given a matrix representing a grid with cells and hurdles, we want to find the longest possible route from a specified source cell to a destination cell. Each cell can be either open (denoted by '1') or blocked by a hurdle (denoted by '0'). Movement is allowed only to adjacent open cells (up, down, left, or right), and the goal is to find the maximum number of steps taken to reach the destination while avoiding hurdles.

Idea to Solve the Problem

To solve this problem, we can use a depth-first search (DFS) approach with backtracking. We start from the source cell, explore all possible paths by moving in the allowed directions, and keep track of the maximum length achieved. We also need to ensure that we don't visit the same cell multiple times and avoid moving to cells blocked by hurdles.

Pseudocode

maxValue(a, b):
    if a > b:
        return a
    else:
        return b

longestPath(matrix, track, i, j, x, y):
    if invalid position (i.e., out of bounds or blocked):
        return -1
    if reached destination (i == x and j == y):
        return 0
    if track[i][j] == 1 or matrix[i][j] == 0:
        return -1
    track[i][j] = 1
    down = longestPath(matrix, track, i + 1, j, x, y)
    right = longestPath(matrix, track, i, j + 1, x, y)
    left = longestPath(matrix, track, i, j - 1, x, y)
    up = longestPath(matrix, track, i - 1, j, x, y)
    track[i][j] = 0
    result = maxValue(left, right)
    result = maxValue(result, up)
    result = maxValue(result, down)
    return result + 1

findLongestPath(matrix, x, y):
    initialize track matrix with all zeros
    result = -1
    if source is the same as destination:
        result = 0
    else:
        result = longestPath(matrix, track, 0, 0, x, y)
    if result == -1:
        print "No path"
    else:
        print result

Algorithm Explanation

  1. maxValue(a, b) is a utility function that returns the maximum of two values.

  2. longestPath(matrix, track, i, j, x, y) is the main recursive function. It takes the matrix, a tracking matrix track to avoid revisiting cells, the current position (i, j), and the destination position (x, y).

  3. We check for invalid positions (out of bounds or blocked cells), and if the current cell is the destination, we return 0 as we've reached the destination.

  4. If the cell is already visited or blocked, we return -1.

  5. We mark the current cell as visited (track[i][j] = 1) to avoid revisiting it.

  6. We recursively explore all four possible directions (up, down, left, right) and calculate the longest path length by taking the maximum of the lengths from each direction.

  7. We reset the tracking cell back to 0 before returning.

  8. findLongestPath(matrix, x, y) initializes the tracking matrix and calculates the longest path using the longestPath function. If no path is found, it prints "No path."

Code Solution

// C Program
// Longest possible route in a matrix with hurdles
#include <stdio.h>
#define N 4
#define M 5

int maxValue(int a, int b)
{
    if(a > b)
    {
        return a;
    }
    else
    {
        return b;
    }
}
int longestPath(int matrix[N][M],int track[N][M],int i, int j, int x, int y)
{   

    if(x >= N || y >= M || x < 0 || y < 0 ||
        i < 0 || j < 0 || i >= N || j >= M)
    {
        // invalid position
        return -1;
    }
    
    if(i == x && j==y)
    {
        // Reached to destination position
        return 0;
    }
    if(track[i][j] == 1 || matrix[i][j] == 0)
    {
        return -1;
    }
    // Active track path value
    track[i][j] = 1;

    // visit to down row
    int down = longestPath(matrix,track,i+1,j,x,y);
    // visit to next col    
    int right = longestPath(matrix,track,i,j+1,x,y);
    // visit to previous column  
    int left = longestPath(matrix,track,i,j-1,x,y);
    // visit to up row  
    int up = longestPath(matrix,track,i-1,j,x,y);

    // Reset value
    track[i][j] = 0;

    int result = maxValue(left,right);

    result = maxValue(result,up);

    result = maxValue(result,down);

   
    return result + 1;  

}

void findLongestPath(int matrix[N][M], int x,int y)
{

    int track[N][M];

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            track[i][j] = 0;
        }
    }

    int result = -1;

    if(x==0 && y == 0)
    {
        //Source and destination are same point
        result = 0;
    }
    else
    {
        result = longestPath(matrix,track,0,0,x,y);
    }

    if(result==-1)
    {
        printf("\n No path");
    }
    else
    {
        printf("\n %d",result);
    }
}

int main()
{

   
    int matrix[N][M] = 
    { 
        { 1, 1, 1, 1, 1 }, 
        { 1, 1, 0, 1, 0 }, 
        { 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1 }
    }; 
    /*
        Source [0][0]
        Destination [2][1]
        --------------------
        1 → 1 → 1 → 1   1  
                    ↓
        1 → 1   0   1   0  
        ↑   ↓       ↓
        1   1   1   1 → 1 
        ↑               ↓
        1 ← 1 ← 1 ← 1 ← 1 
        -----------------
        Result = 15 
        Note that there is more than one solution possible
    */

    findLongestPath(matrix,2,1);
    /*
        Source [0][0]
        Destination [2][3]
        --------------------
        1 → 1   1   1   1  
            ↓        
        1 ← 1   0   1   0  
        ↓            
        1   1 → 1   1 ← 1 
        ↓   ↑   ↓       ↑
        1 → 1   1 → 1 → 1 
        -----------------
        Result = 13
    */
    findLongestPath(matrix,2,3);


    /*
        Source [0][0]
        Destination [0][2]
        --------------------
        1 → 1   1 ← 1   1  
            ↓       ↑
        1 ← 1   0   1   0  
        ↓           ↑
        1   1 → 1   1 ← 1 
        ↓   ↑   ↓       ↑
        1 → 1   1 → 1 → 1 
        -----------------
        Result = 16 
    */
    findLongestPath(matrix,0,2);
    return 0;
}

Output

 15
 13
 16
/*
    Java Program for
    Longest possible route in a matrix with hurdles
*/

public class Path
{
    
    public int maxValue(int a, int b)
    {
        if (a > b)
        {
            return a;
        }
        else
        {
            return b;
        }
    }
    public int longestPath(int[][] matrix, boolean[][] track, 
        int i, int j, int x, int y, int n, int m)
    {
        if (x >= n || y >= m || x < 0 || y < 0 || i < 0 || 
            j < 0 || i >= n || j >= m)
        {
            // invalid position
            return -1;
        }
        if (i == x && j == y)
        {
            // Reached to destination position
            return 0;
        }
        if (track[i][j] == true || matrix[i][j] == 0)
        {
            return -1;
        }
        // Active track path value
        track[i][j] = true;
        // visit to down row
        int down = longestPath(matrix, track, i + 1, j, x, y, n,m);
        // visit to next column    
        int right = longestPath(matrix, track, i, j + 1, x, y, n,m);
        // visit to previous column  
        int left = longestPath(matrix, track, i, j - 1, x, y, n,m);
        // visit to up row  
        int up = longestPath(matrix, track, i - 1, j, x, y, n,m);
        // Reset value
        track[i][j] = false;
        int result = maxValue(left, right);
        result = maxValue(result, up);
        result = maxValue(result, down);
        return result + 1;
    }
    public void findLongestPath(int[][] matrix, int x, int y)
    {
        int n = matrix.length;
        int m = matrix[0].length;
        boolean[][] track = new boolean[n][m];
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                track[i][j] = false;
            }
        }
        int result = -1;
        if (x == 0 && y == 0)
        {
            //Source and destination are same point
            result = 0;
        }
        else
        {
            result = longestPath(matrix, track, 0, 0, x, y, n, m);
        }
        if (result == -1)
        {
            System.out.print("\n No path");
        }
        else
        {
            System.out.print("\n " + result );
        }
    }
    public static void main(String[] args)
    {
        Path task = new Path();

        int[][] matrix  = 
        {
            {
                1 , 1 , 1 , 1 , 1
            } , 
            {
                1 , 1 , 0 , 1 , 0
            } , 
            {
                1 , 1 , 1 , 1 , 1
            } , 
            {
                1 , 1 , 1 , 1 , 1
            }
        };
        /*
            Source [0][0]
            Destination [2][1]
            --------------------
            1 → 1 → 1 → 1   1  
                        ↓
            1 → 1   0   1   0  
            ↑   ↓       ↓
            1   1   1   1 → 1 
            ↑               ↓
            1 ← 1 ← 1 ← 1 ← 1 
            -----------------
            Result = 15 
            --------------------
            Note that there is more than one solution possible
        */

        task.findLongestPath(matrix, 2, 1);


        /*
            Source [0][0]
            Destination [2][3]
            --------------------
            1 → 1   1   1   1  
                ↓        
            1 ← 1   0   1   0  
            ↓            
            1   1 → 1   1 ← 1 
            ↓   ↑   ↓       ↑
            1 → 1   1 → 1 → 1 
            -----------------
            Result = 13
        */
        task.findLongestPath(matrix, 2, 3);
        /*
            Source [0][0]
            Destination [0][2]
            --------------------
            1 → 1   1 ← 1   1  
                ↓       ↑
            1 ← 1   0   1   0  
            ↓           ↑
            1   1 → 1   1 ← 1 
            ↓   ↑   ↓       ↑
            1 → 1   1 → 1 → 1 
            -----------------
            Result = 16 
        */
        task.findLongestPath(matrix, 0, 2);

    }
}

Output

 15
 13
 16
// Include header file
#include <iostream>
#define N 4
#define M 5
using namespace std;
/*
    C++ Program for
    Longest possible route in a matrix with hurdles
*/
class Path
{
    public: int maxValue(int a, int b)
    {
        if (a > b)
        {
            return a;
        }
        else
        {
            return b;
        }
    }
    int longestPath(int matrix[N][M], bool track[N][M], 
      int i, int j, int x, int y)
    {
        if (x >= N || y >= M || x < 0 || y < 0 || 
            i < 0 || j < 0 || i >= N || j >= M)
        {
            // invalid position
            return -1;
        }
        if (i == x && j == y)
        {
            // Reached to destination position
            return 0;
        }
        if (track[i][j] == true || matrix[i][j] == 0)
        {
            return -1;
        }
        // Active track path value
        track[i][j] = true;
        // visit to down row
        int down = this->longestPath(matrix, track, i + 1, j, x, y);
        // visit to next column    
        int right = this->longestPath(matrix, track, i, j + 1, x, y);
        // visit to previous column  
        int left = this->longestPath(matrix, track, i, j - 1, x, y);
        // visit to up row  
        int up = this->longestPath(matrix, track, i - 1, j, x, y);
        // Reset value
        track[i][j] = false;
        int result = this->maxValue(left, right);
        result = this->maxValue(result, up);
        result = this->maxValue(result, down);
        return result + 1;
    }
    void findLongestPath(int matrix[N][M], int x, int y)
    {

        bool track[N][M];
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < M; ++j)
            {
                track[i][j] = false;
            }
        }
        int result = -1;
        if (x == 0 && y == 0)
        {
            //Source and destination are same point
            result = 0;
        }
        else
        {
            result = this->longestPath(matrix, track, 0, 0, x, y);
        }
        if (result == -1)
        {
            cout << "\n No path";
        }
        else
        {
            cout << "\n " << result;
        }
    }
};
int main()
{
    Path *task = new Path();
    int matrix[N][M] = {
        {
            1 , 1 , 1 , 1 , 1
        } , {
            1 , 1 , 0 , 1 , 0
        } , {
            1 , 1 , 1 , 1 , 1
        } , {
            1 , 1 , 1 , 1 , 1
        }
    };
    /*
        Source [0][0]
        Destination [2][1]
        --------------------
        1 → 1 → 1 → 1   1  
                    ↓
        1 → 1   0   1   0  
        ↑   ↓       ↓
        1   1   1   1 → 1 
        ↑               ↓
        1 ← 1 ← 1 ← 1 ← 1 
        -----------------
        Result = 15 
        --------------------
        Note that there is more than one solution possible
    */
    task->findLongestPath(matrix, 2, 1);
    /*
        Source [0][0]
        Destination [2][3]
        --------------------
        1 → 1   1   1   1  
            ↓        
        1 ← 1   0   1   0  
        ↓            
        1   1 → 1   1 ← 1 
        ↓   ↑   ↓       ↑
        1 → 1   1 → 1 → 1 
        -----------------
        Result = 13
    */
    task->findLongestPath(matrix, 2, 3);
    /*
        Source [0][0]
        Destination [0][2]
        --------------------
        1 → 1   1 ← 1   1  
            ↓       ↑
        1 ← 1   0   1   0  
        ↓           ↑
        1   1 → 1   1 ← 1 
        ↓   ↑   ↓       ↑
        1 → 1   1 → 1 → 1 
        -----------------
        Result = 16 
    */
    task->findLongestPath(matrix, 0, 2);
    return 0;
}

Output

 15
 13
 16
// Include namespace system
using System;
/*
    Csharp Program for
    Longest possible route in a matrix with hurdles
*/
public class Path
{
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	public int longestPath(int[,] matrix, Boolean[,] track, 
  		int i, int j, int x, int y, int n, int m)
	{
		if (x >= n || y >= m || x < 0 || y < 0 || 
            i < 0 || j < 0 || i >= n || j >= m)
		{
			// invalid position
			return -1;
		}
		if (i == x && j == y)
		{
			// Reached to destination position
			return 0;
		}
		if (track[i,j] == true || matrix[i,j] == 0)
		{
			return -1;
		}
		// Active track path value
		track[i,j] = true;
		// visit to down row
		int down = this.longestPath(matrix, track, i + 1, j, x, y, n, m);
		// visit to next column    
		int right = this.longestPath(matrix, track, i, j + 1, x, y, n, m);
		// visit to previous column  
		int left = this.longestPath(matrix, track, i, j - 1, x, y, n, m);
		// visit to up row  
		int up = this.longestPath(matrix, track, i - 1, j, x, y, n, m);
		// Reset value
		track[i,j] = false;
		int result = this.maxValue(left, right);
		result = this.maxValue(result, up);
		result = this.maxValue(result, down);
		return result + 1;
	}
	public void findLongestPath(int[,] matrix, int x, int y)
	{
		int n = matrix.GetLength(0);
		int m = matrix.GetLength(1);
		Boolean[,] track = new Boolean[n,m];
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				track[i,j] = false;
			}
		}
		int result = -1;
		if (x == 0 && y == 0)
		{
			//Source and destination are same point
			result = 0;
		}
		else
		{
			result = this.longestPath(matrix, track, 0, 0, x, y, n, m);
		}
		if (result == -1)
		{
			Console.Write("\n No path");
		}
		else
		{
			Console.Write("\n " + result);
		}
	}
	public static void Main(String[] args)
	{
		Path task = new Path();
		int[,] matrix = {
			{
				1 , 1 , 1 , 1 , 1
			},
{
				1 , 1 , 0 , 1 , 0
			},
{
				1 , 1 , 1 , 1 , 1
			},
{
				1 , 1 , 1 , 1 , 1
			}
		};
		/*
		            Source [0,0]
		            Destination [2,1]
		            --------------------
		            1 → 1 → 1 → 1   1  
		                        ↓
		            1 → 1   0   1   0  
		            ↑   ↓       ↓
		            1   1   1   1 → 1 
		            ↑               ↓
		            1 ← 1 ← 1 ← 1 ← 1 
		            -----------------
		            Result = 15 
		            --------------------
		            Note that there is more than one solution possible
		        */
		task.findLongestPath(matrix, 2, 1);
		/*
		            Source [0,0]
		            Destination [2,3]
		            --------------------
		            1 → 1   1   1   1  
		                ↓        
		            1 ← 1   0   1   0  
		            ↓            
		            1   1 → 1   1 ← 1 
		            ↓   ↑   ↓       ↑
		            1 → 1   1 → 1 → 1 
		            -----------------
		            Result = 13
		        */
		task.findLongestPath(matrix, 2, 3);
		/*
		            Source [0,0]
		            Destination [0,2]
		            --------------------
		            1 → 1   1 ← 1   1  
		                ↓       ↑
		            1 ← 1   0   1   0  
		            ↓           ↑
		            1   1 → 1   1 ← 1 
		            ↓   ↑   ↓       ↑
		            1 → 1   1 → 1 → 1 
		            -----------------
		            Result = 16 
		        */
		task.findLongestPath(matrix, 0, 2);
	}
}

Output

 15
 13
 16
package main
import "fmt"
/*
    Go Program for
    Longest possible route in a matrix with hurdles
*/
type Path struct {}
func getPath() * Path {
	var me *Path = &Path {}
	return me
}
func(this Path) maxValue(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}
func(this Path) longestPath(matrix[][] int, track[][] bool,
	 i int, j int, x int, y int, n int, m int) int {
	if x >= n || y >= m || 
		x < 0 || y < 0 || i < 0 || j < 0 || i >= n || j >= m {
		// invalid position
		return -1
	}
	if i == x && j == y {
		// Reached to destination position
		return 0
	}
	if track[i][j] == true || matrix[i][j] == 0 {
		return -1
	}
	// Active track path value
	track[i][j] = true
	// visit to down row
	var down int = this.longestPath(matrix, track, i + 1, j, x, y, n, m)
	// visit to next column
	var right int = this.longestPath(matrix, track, i, j + 1, x, y, n, m)
	// visit to previous column
	var left int = this.longestPath(matrix, track, i, j - 1, x, y, n, m)
	// visit to up row
	var up int = this.longestPath(matrix, track, i - 1, j, x, y, n, m)
	// Reset value
	track[i][j] = false
	var result int = this.maxValue(left, right)
	result = this.maxValue(result, up)
	result = this.maxValue(result, down)
	return result + 1
}
func(this Path) findLongestPath(matrix[][] int, x int, y int) {
	var n int = len(matrix)
	var m int = len(matrix[0])
	var track = make([][] bool, n)
	for i:= 0;i < n;i++ {
		track[i] = make([]bool,m)
	}
	var result int = -1
	if x == 0 && y == 0 {
		//Source and destination are same point
		result = 0
	} else {
		result = this.longestPath(matrix, track, 0, 0, x, y, n, m)
	}
	if result == -1 {
		fmt.Print("\n No path")
	} else {
		fmt.Print("\n ", result)
	}
}
func main() {
	var task * Path = getPath()
	var matrix = [][] int {{ 1, 1, 1, 1, 1 }, 
        { 1, 1, 0, 1, 0 }, 
        { 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1 }}
	/*
	    Source [0][0]
	    Destination [2][1]
	    --------------------
	    1 → 1 → 1 → 1   1  
	                ↓
	    1 → 1   0   1   0  
	    ↑   ↓       ↓
	    1   1   1   1 → 1 
	    ↑               ↓
	    1 ← 1 ← 1 ← 1 ← 1 
	    -----------------
	    Result = 15 
	    --------------------
	    Note that there is more than one solution possible
	*/
	task.findLongestPath(matrix, 2, 1)
	/*
	    Source [0][0]
	    Destination [2][3]
	    --------------------
	    1 → 1   1   1   1  
	        ↓        
	    1 ← 1   0   1   0  
	    ↓            
	    1   1 → 1   1 ← 1 
	    ↓   ↑   ↓       ↑
	    1 → 1   1 → 1 → 1 
	    -----------------
	    Result = 13
	*/
	task.findLongestPath(matrix, 2, 3)
	/*
	    Source [0][0]
	    Destination [0][2]
	    --------------------
	    1 → 1   1 ← 1   1  
	        ↓       ↑
	    1 ← 1   0   1   0  
	    ↓           ↑
	    1   1 → 1   1 ← 1 
	    ↓   ↑   ↓       ↑
	    1 → 1   1 → 1 → 1 
	    -----------------
	    Result = 16 
	*/
	task.findLongestPath(matrix, 0, 2)
}

Output

 15
 13
 16
<?php
/*
    Php Program for
    Longest possible route in a matrix with hurdles
*/
class Path
{
	public	function maxValue($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	public	function longestPath($matrix, &$track, $i, $j, $x, $y, $n, $m)
	{
		if ($x >= $n || $y >= $m || $x < 0 || $y < 0 || 
            $i < 0 || $j < 0 || $i >= $n || $j >= $m)
		{
			// invalid position
			return -1;
		}
		if ($i == $x && $j == $y)
		{
			// Reached to destination position
			return 0;
		}
		if ($track[$i][$j] == true || $matrix[$i][$j] == 0)
		{
			return -1;
		}
		// Active track path value
		$track[$i][$j] = true;
		// visit to down row
		$down = $this->longestPath($matrix, $track, $i + 1, $j, $x, $y, $n, $m);
		// visit to next column
		$right = $this->longestPath($matrix, $track, $i, $j + 1, $x, $y, $n, $m);
		// visit to previous column
		$left = $this->longestPath($matrix, $track, $i, $j - 1, $x, $y, $n, $m);
		// visit to up row
		$up = $this->longestPath($matrix, $track, $i - 1, $j, $x, $y, $n, $m);
		// Reset value
		$track[$i][$j] = false;
		$result = $this->maxValue($left, $right);
		$result = $this->maxValue($result, $up);
		$result = $this->maxValue($result, $down);
		return $result + 1;
	}
	public	function findLongestPath($matrix, $x, $y)
	{
		$n = count($matrix);
		$m = count($matrix[0]);
		$track = array_fill(0, $n, array_fill(0, $m, false));
		$result = -1;
		if ($x == 0 && $y == 0)
		{
			//Source and destination are same point
			$result = 0;
		}
		else
		{
			$result = $this->longestPath($matrix, $track, 0, 0, $x, $y, $n, $m);
		}
		if ($result == -1)
		{
			echo("\n No path");
		}
		else
		{
			echo("\n ".$result);
		}
	}
}

function main()
{
	$task = new Path();
	$matrix = array(
      array(1, 1, 1, 1, 1), 
      array(1, 1, 0, 1, 0), 
      array(1, 1, 1, 1, 1), 
      array(1, 1, 1, 1, 1)
    );
	/*
	    Source [0][0]
	    Destination [2][1]
	    --------------------
	    1 → 1 → 1 → 1   1  
	                ↓
	    1 → 1   0   1   0  
	    ↑   ↓       ↓
	    1   1   1   1 → 1 
	    ↑               ↓
	    1 ← 1 ← 1 ← 1 ← 1 
	    -----------------
	    Result = 15 
	    --------------------
	    Note that there is more than one solution possible
	*/
	$task->findLongestPath($matrix, 2, 1);
	/*
	    Source [0][0]
	    Destination [2][3]
	    --------------------
	    1 → 1   1   1   1  
	        ↓        
	    1 ← 1   0   1   0  
	    ↓            
	    1   1 → 1   1 ← 1 
	    ↓   ↑   ↓       ↑
	    1 → 1   1 → 1 → 1 
	    -----------------
	    Result = 13
	*/
	$task->findLongestPath($matrix, 2, 3);
	/*
	    Source [0][0]
	    Destination [0][2]
	    --------------------
	    1 → 1   1 ← 1   1  
	        ↓       ↑
	    1 ← 1   0   1   0  
	    ↓           ↑
	    1   1 → 1   1 ← 1 
	    ↓   ↑   ↓       ↑
	    1 → 1   1 → 1 → 1 
	    -----------------
	    Result = 16 
	*/
	$task->findLongestPath($matrix, 0, 2);
}
main();

Output

 15
 13
 16
/*
    Node JS Program for
    Longest possible route in a matrix with hurdles
*/
class Path
{
	maxValue(a, b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	longestPath(matrix, track, i, j, x, y, n, m)
	{
		if (x >= n || y >= m || x < 0 || y < 0 || 
            i < 0 || j < 0 || i >= n || j >= m)
		{
			// invalid position
			return -1;
		}
		if (i == x && j == y)
		{
			// Reached to destination position
			return 0;
		}
		if (track[i][j] == true || matrix[i][j] == 0)
		{
			return -1;
		}
		// Active track path value
		track[i][j] = true;
		// visit to down row
		var down = this.longestPath(matrix, track, i + 1, j, x, y, n, m);
		// visit to next column
		var right = this.longestPath(matrix, track, i, j + 1, x, y, n, m);
		// visit to previous column
		var left = this.longestPath(matrix, track, i, j - 1, x, y, n, m);
		// visit to up row
		var up = this.longestPath(matrix, track, i - 1, j, x, y, n, m);
		// Reset value
		track[i][j] = false;
		var result = this.maxValue(left, right);
		result = this.maxValue(result, up);
		result = this.maxValue(result, down);
		return result + 1;
	}
	findLongestPath(matrix, x, y)
	{
		var n = matrix.length;
		var m = matrix[0].length;
		var track = Array(n).fill(false).map(() => new Array(m).fill(false));
		var result = -1;
		if (x == 0 && y == 0)
		{
			//Source and destination are same point
			result = 0;
		}
		else
		{
			result = this.longestPath(matrix, track, 0, 0, x, y, n, m);
		}
		if (result == -1)
		{
			process.stdout.write("\n No path");
		}
		else
		{
			process.stdout.write("\n " + result);
		}
	}
}

function main()
{
	var task = new Path();
	var matrix = [
		[1, 1, 1, 1, 1],
		[1, 1, 0, 1, 0],
		[1, 1, 1, 1, 1],
		[1, 1, 1, 1, 1]
	];
	/*
	    Source [0][0]
	    Destination [2][1]
	    --------------------
	    1 → 1 → 1 → 1   1  
	                ↓
	    1 → 1   0   1   0  
	    ↑   ↓       ↓
	    1   1   1   1 → 1 
	    ↑               ↓
	    1 ← 1 ← 1 ← 1 ← 1 
	    -----------------
	    Result = 15 
	    --------------------
	    Note that there is more than one solution possible
	*/
	task.findLongestPath(matrix, 2, 1);
	/*
	    Source [0][0]
	    Destination [2][3]
	    --------------------
	    1 → 1   1   1   1  
	        ↓        
	    1 ← 1   0   1   0  
	    ↓            
	    1   1 → 1   1 ← 1 
	    ↓   ↑   ↓       ↑
	    1 → 1   1 → 1 → 1 
	    -----------------
	    Result = 13
	*/
	task.findLongestPath(matrix, 2, 3);
	/*
	    Source [0][0]
	    Destination [0][2]
	    --------------------
	    1 → 1   1 ← 1   1  
	        ↓       ↑
	    1 ← 1   0   1   0  
	    ↓           ↑
	    1   1 → 1   1 ← 1 
	    ↓   ↑   ↓       ↑
	    1 → 1   1 → 1 → 1 
	    -----------------
	    Result = 16 
	*/
	task.findLongestPath(matrix, 0, 2);
}
main();

Output

 15
 13
 16
#    Python 3 Program for
#    Longest possible route in a matrix with hurdles
class Path :
	def maxValue(self, a, b) :
		if (a > b) :
			return a
		else :
			return b
		
	
	def longestPath(self, matrix, track, i, j, x, y, n, m) :
		if (x >= n or y >= m or x < 0 or y < 0 or 
            i < 0 or j < 0 or i >= n or j >= m) :
			#  invalid position
			return -1
		
		if (i == x and j == y) :
			#  Reached to destination position
			return 0
		
		if (track[i][j] == True or matrix[i][j] == 0) :
			return -1
		
		#  Active track path value
		track[i][j] = True
		#  visit to down row
		down = self.longestPath(matrix, track, i + 1, j, x, y, n, m)
		#  visit to next column
		right = self.longestPath(matrix, track, i, j + 1, x, y, n, m)
		#  visit to previous column
		left = self.longestPath(matrix, track, i, j - 1, x, y, n, m)
		#  visit to up row
		up = self.longestPath(matrix, track, i - 1, j, x, y, n, m)
		#  Reset value
		track[i][j] = False
		result = self.maxValue(left, right)
		result = self.maxValue(result, up)
		result = self.maxValue(result, down)
		return result + 1
	
	def findLongestPath(self, matrix, x, y) :
		n = len(matrix)
		m = len(matrix[0])
		track = [[False] * (m) for _ in range(n) ]
		result = -1
		if (x == 0 and y == 0) :
			# Source and destination are same point
			result = 0
		else :
			result = self.longestPath(matrix, track, 0, 0, x, y, n, m)
		
		if (result == -1) :
			print("\n No path", end = "")
		else :
			print("\n ", result, end = "")
		
	

def main() :
	task = Path()
	matrix = [
		[1, 1, 1, 1, 1],
		[1, 1, 0, 1, 0],
		[1, 1, 1, 1, 1],
		[1, 1, 1, 1, 1]
	]
	#    Source [0][0]
	#    Destination [2][1]
	#    --------------------
	#    1 → 1 → 1 → 1   1  
	#                ↓
	#    1 → 1   0   1   0  
	#    ↑   ↓       ↓
	#    1   1   1   1 → 1 
	#    ↑               ↓
	#    1 ← 1 ← 1 ← 1 ← 1 
	#    -----------------
	#    Result = 15 
	#    --------------------
	#    Note that there is more than one solution possible
	task.findLongestPath(matrix, 2, 1)
	#    Source [0][0]
	#    Destination [2][3]
	#    --------------------
	#    1 → 1   1   1   1  
	#        ↓        
	#    1 ← 1   0   1   0  
	#    ↓            
	#    1   1 → 1   1 ← 1 
	#    ↓   ↑   ↓       ↑
	#    1 → 1   1 → 1 → 1 
	#    -----------------
	#    Result = 13
	task.findLongestPath(matrix, 2, 3)
	#    Source [0][0]
	#    Destination [0][2]
	#    --------------------
	#    1 → 1   1 ← 1   1  
	#        ↓       ↑
	#    1 ← 1   0   1   0  
	#    ↓           ↑
	#    1   1 → 1   1 ← 1 
	#    ↓   ↑   ↓       ↑
	#    1 → 1   1 → 1 → 1 
	#    -----------------
	#    Result = 16 
	task.findLongestPath(matrix, 0, 2)

if __name__ == "__main__": main()

Output

  15
  13
  16
#    Ruby Program for
#    Longest possible route in a matrix with hurdles
class Path 
	def maxValue(a, b) 
		if (a > b) 
			return a
		else
 
			return b
		end

	end

	def longestPath(matrix, track, i, j, x, y, n, m) 
		if (x >= n || y >= m || x < 0 || y < 0 || i < 0 || 
            j < 0 || i >= n || j >= m) 
			#  invalid position
			return -1
		end

		if (i == x && j == y) 
			#  Reached to destination position
			return 0
		end

		if (track[i][j] == true || matrix[i][j] == 0) 
			return -1
		end

		#  Active track path value
		track[i][j] = true
		#  visit to down row
		down = self.longestPath(matrix, track, i + 1, j, x, y, n, m)
		#  visit to next column
		right = self.longestPath(matrix, track, i, j + 1, x, y, n, m)
		#  visit to previous column
		left = self.longestPath(matrix, track, i, j - 1, x, y, n, m)
		#  visit to up row
		up = self.longestPath(matrix, track, i - 1, j, x, y, n, m)
		#  Reset value
		track[i][j] = false
		result = self.maxValue(left, right)
		result = self.maxValue(result, up)
		result = self.maxValue(result, down)
		return result + 1
	end

	def findLongestPath(matrix, x, y) 
		n = matrix.length
		m = matrix[0].length
		track = Array.new(n) {Array.new(m) {false}}
		result = -1
		if (x == 0 && y == 0) 
			# Source and destination are same point
			result = 0
		else
 
			result = self.longestPath(matrix, track, 0, 0, x, y, n, m)
		end

		if (result == -1) 
			print("\n No path")
		else
 
			print("\n ", result)
		end

	end

end

def main() 
	task = Path.new()
	matrix = [
		[1, 1, 1, 1, 1],
		[1, 1, 0, 1, 0],
		[1, 1, 1, 1, 1],
		[1, 1, 1, 1, 1]
	]
	#    Source [0][0]
	#    Destination [2][1]
	#    --------------------
	#    1 → 1 → 1 → 1   1  
	#                ↓
	#    1 → 1   0   1   0  
	#    ↑   ↓       ↓
	#    1   1   1   1 → 1 
	#    ↑               ↓
	#    1 ← 1 ← 1 ← 1 ← 1 
	#    -----------------
	#    Result = 15 
	#    --------------------
	#    Note that there is more than one solution possible
	task.findLongestPath(matrix, 2, 1)
	#    Source [0][0]
	#    Destination [2][3]
	#    --------------------
	#    1 → 1   1   1   1  
	#        ↓        
	#    1 ← 1   0   1   0  
	#    ↓            
	#    1   1 → 1   1 ← 1 
	#    ↓   ↑   ↓       ↑
	#    1 → 1   1 → 1 → 1 
	#    -----------------
	#    Result = 13
	task.findLongestPath(matrix, 2, 3)
	#    Source [0][0]
	#    Destination [0][2]
	#    --------------------
	#    1 → 1   1 ← 1   1  
	#        ↓       ↑
	#    1 ← 1   0   1   0  
	#    ↓           ↑
	#    1   1 → 1   1 ← 1 
	#    ↓   ↑   ↓       ↑
	#    1 → 1   1 → 1 → 1 
	#    -----------------
	#    Result = 16 
	task.findLongestPath(matrix, 0, 2)
end

main()

Output

 15
 13
 16
/*
    Scala Program for
    Longest possible route in a matrix with hurdles
*/
class Path()
{
	def maxValue(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	def longestPath(
      matrix: Array[Array[Int]], 
      track: Array[Array[Boolean]], 
        i: Int, j: Int, x: Int, y: Int, 
          n: Int, m: Int): Int = {
		if (x >= n || y >= m || x < 0 || y < 0 || 
             i < 0 || j < 0 || i >= n || j >= m)
		{
			// invalid position
			return -1;
		}
		if (i == x && j == y)
		{
			// Reached to destination position
			return 0;
		}
		if (track(i)(j) == true || matrix(i)(j) == 0)
		{
			return -1;
		}
		// Active track path value
		track(i)(j) = true;
		// visit to down row
		var down: Int = longestPath(matrix, track, i + 1, j, x, y, n, m);
		// visit to next column
		var right: Int = longestPath(matrix, track, i, j + 1, x, y, n, m);
		// visit to previous column
		var left: Int = longestPath(matrix, track, i, j - 1, x, y, n, m);
		// visit to up row
		var up: Int = longestPath(matrix, track, i - 1, j, x, y, n, m);
		// Reset value
		track(i)(j) = false;
		var result: Int = maxValue(left, right);
		result = maxValue(result, up);
		result = maxValue(result, down);
		return result + 1;
	}
	def findLongestPath(matrix: Array[Array[Int]], x: Int, y: Int): Unit = {
		var n: Int = matrix.length;
		var m: Int = matrix(0).length;
		var track: Array[Array[Boolean]] = Array.fill[Boolean](n, m)(false);
		var result: Int = -1;
		if (x == 0 && y == 0)
		{
			//Source and destination are same point
			result = 0;
		}
		else
		{
			result = longestPath(matrix, track, 0, 0, x, y, n, m);
		}
		if (result == -1)
		{
			print("\n No path");
		}
		else
		{
			print("\n " + result);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Path = new Path();
		var matrix: Array[Array[Int]] = Array(
          Array(1, 1, 1, 1, 1), 
          Array(1, 1, 0, 1, 0), 
          Array(1, 1, 1, 1, 1),
          Array(1, 1, 1, 1, 1)
        );
		/*
		    Source [0][0]
		    Destination [2][1]
		    --------------------
		    1 → 1 → 1 → 1   1  
		                ↓
		    1 → 1   0   1   0  
		    ↑   ↓       ↓
		    1   1   1   1 → 1 
		    ↑               ↓
		    1 ← 1 ← 1 ← 1 ← 1 
		    -----------------
		    Result = 15 
		    --------------------
		    Note that there is more than one solution possible
		*/
		task.findLongestPath(matrix, 2, 1);
		/*
		    Source [0][0]
		    Destination [2][3]
		    --------------------
		    1 → 1   1   1   1  
		        ↓        
		    1 ← 1   0   1   0  
		    ↓            
		    1   1 → 1   1 ← 1 
		    ↓   ↑   ↓       ↑
		    1 → 1   1 → 1 → 1 
		    -----------------
		    Result = 13
		*/
		task.findLongestPath(matrix, 2, 3);
		/*
		    Source [0][0]
		    Destination [0][2]
		    --------------------
		    1 → 1   1 ← 1   1  
		        ↓       ↑
		    1 ← 1   0   1   0  
		    ↓           ↑
		    1   1 → 1   1 ← 1 
		    ↓   ↑   ↓       ↑
		    1 → 1   1 → 1 → 1 
		    -----------------
		    Result = 16 
		*/
		task.findLongestPath(matrix, 0, 2);
	}
}

Output

 15
 13
 16
import Foundation;
/*
    Swift 4 Program for
    Longest possible route in a matrix with hurdles
*/
class Path
{
	func maxValue(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	func longestPath(_ matrix: [[Int]], _ track: inout[[Bool]], 
      _ i: Int, _ j: Int, _ x: Int, _ y: Int, _ n: Int, _ m: Int) -> Int
	{
		if (x >= n || y >= m || x < 0 || y < 0 || 
            i < 0 || j < 0 || i >= n || j >= m)
		{
			// invalid position
			return -1;
		}
		if (i == x && j == y)
		{
			// Reached to destination position
			return 0;
		}
		if (track[i][j] == true || matrix[i][j] == 0)
		{
			return -1;
		}
		// Active track path value
		track[i][j] = true;
		// visit to down row
		let down: Int = 
          self.longestPath(matrix, &track, i + 1, j, x, y, n, m);
		// visit to next column
		let right: Int = 
          self.longestPath(matrix, &track, i, j + 1, x, y, n, m);
		// visit to previous column
		let left: Int = 
          self.longestPath(matrix, &track, i, j - 1, x, y, n, m);
		// visit to up row
		let up: Int = 
          self.longestPath(matrix, &track, i - 1, j, x, y, n, m);
		// Reset value
		track[i][j] = false;
		var result: Int = self.maxValue(left, right);
		result = self.maxValue(result, up);
		result = self.maxValue(result, down);
		return result + 1;
	}
	func findLongestPath(_ matrix: [[Int]], _ x: Int, _ y: Int)
	{
		let n: Int = matrix.count;
		let m: Int = matrix[0].count;
		var track: [
			[Bool]
		] = Array(repeating: Array(repeating: false, count: m), count: n);
		var result: Int = -1;
		if (x == 0 && y == 0)
		{
			//Source and destination are same point
			result = 0;
		}
		else
		{
			result = self.longestPath(matrix, &track, 0, 0, x, y, n, m);
		}
		if (result == -1)
		{
			print("\n No path", terminator: "");
		}
		else
		{
			print("\n ", result, terminator: "");
		}
	}
}
func main()
{
	let task: Path = Path();
	let matrix: [
		[Int]
	] = [
		[1, 1, 1, 1, 1],
		[1, 1, 0, 1, 0],
		[1, 1, 1, 1, 1],
		[1, 1, 1, 1, 1]
	];
	/*
	    Source [0][0]
	    Destination [2][1]
	    --------------------
	    1 → 1 → 1 → 1   1  
	                ↓
	    1 → 1   0   1   0  
	    ↑   ↓       ↓
	    1   1   1   1 → 1 
	    ↑               ↓
	    1 ← 1 ← 1 ← 1 ← 1 
	    -----------------
	    Result = 15 
	    --------------------
	    Note that there is more than one solution possible
	*/
	task.findLongestPath(matrix, 2, 1);
	/*
	    Source [0][0]
	    Destination [2][3]
	    --------------------
	    1 → 1   1   1   1  
	        ↓        
	    1 ← 1   0   1   0  
	    ↓            
	    1   1 → 1   1 ← 1 
	    ↓   ↑   ↓       ↑
	    1 → 1   1 → 1 → 1 
	    -----------------
	    Result = 13
	*/
	task.findLongestPath(matrix, 2, 3);
	/*
	    Source [0][0]
	    Destination [0][2]
	    --------------------
	    1 → 1   1 ← 1   1  
	        ↓       ↑
	    1 ← 1   0   1   0  
	    ↓           ↑
	    1   1 → 1   1 ← 1 
	    ↓   ↑   ↓       ↑
	    1 → 1   1 → 1 → 1 
	    -----------------
	    Result = 16 
	*/
	task.findLongestPath(matrix, 0, 2);
}
main();

Output

  15
  13
  16
/*
    Kotlin Program for
    Longest possible route in a matrix with hurdles
*/
class Path
{
	fun maxValue(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	fun longestPath(matrix: Array < Array < Int >> , 
                    track: Array < Array < Boolean >> , 
                    i: Int, j: Int, x: Int, y: Int, n: Int, m: Int): Int
	{
		if (x >= n || y >= m || x < 0 || y < 0 || i < 0 ||
            j < 0 || i >= n || j >= m)
		{
			// invalid position
			return -1;
		}
		if (i == x && j == y)
		{
			// Reached to destination position
			return 0;
		}
		if (track[i][j] == true || matrix[i][j] == 0)
		{
			return -1;
		}
		// Active track path value
		track[i][j] = true;
		// visit to down row
		val down: Int = this.longestPath(matrix, track, i + 1, j, x, y, n, m);
		// visit to next column
		val right: Int = this.longestPath(matrix, track, i, j + 1, x, y, n, m);
		// visit to previous column
		val left: Int = this.longestPath(matrix, track, i, j - 1, x, y, n, m);
		// visit to up row
		val up: Int = this.longestPath(matrix, track, i - 1, j, x, y, n, m);
		// Reset value
		track[i][j] = false;
		var result: Int = this.maxValue(left, right);
		result = this.maxValue(result, up);
		result = this.maxValue(result, down);
		return result + 1;
	}
	fun findLongestPath(matrix: Array < Array < Int >> , x: Int, y: Int): Unit
	{
		val n: Int = matrix.count();
		val m: Int = matrix[0].count();
		val track: Array < Array < Boolean >> = Array(n)
		{
			Array(m)
			{
				false
			}
		};
		var result: Int ;
		if (x == 0 && y == 0)
		{
			//Source and destination are same point
			result = 0;
		}
		else
		{
			result = this.longestPath(matrix, track, 0, 0, x, y, n, m);
		}
		if (result == -1)
		{
			print("\n No path");
		}
		else
		{
			print("\n " + result);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Path = Path();
	val matrix: Array < Array < Int >> = arrayOf(
      arrayOf(1, 1, 1, 1, 1), 
      arrayOf(1, 1, 0, 1, 0), 
      arrayOf(1, 1, 1, 1, 1), 
      arrayOf(1, 1, 1, 1, 1)
    );
	/*
	    Source [0][0]
	    Destination [2][1]
	    --------------------
	    1 → 1 → 1 → 1   1  
	                ↓
	    1 → 1   0   1   0  
	    ↑   ↓       ↓
	    1   1   1   1 → 1 
	    ↑               ↓
	    1 ← 1 ← 1 ← 1 ← 1 
	    -----------------
	    Result = 15 
	    --------------------
	    Note that there is more than one solution possible
	*/
	task.findLongestPath(matrix, 2, 1);
	/*
	    Source [0][0]
	    Destination [2][3]
	    --------------------
	    1 → 1   1   1   1  
	        ↓        
	    1 ← 1   0   1   0  
	    ↓            
	    1   1 → 1   1 ← 1 
	    ↓   ↑   ↓       ↑
	    1 → 1   1 → 1 → 1 
	    -----------------
	    Result = 13
	*/
	task.findLongestPath(matrix, 2, 3);
	/*
	    Source [0][0]
	    Destination [0][2]
	    --------------------
	    1 → 1   1 ← 1   1  
	        ↓       ↑
	    1 ← 1   0   1   0  
	    ↓           ↑
	    1   1 → 1   1 ← 1 
	    ↓   ↑   ↓       ↑
	    1 → 1   1 → 1 → 1 
	    -----------------
	    Result = 16 
	*/
	task.findLongestPath(matrix, 0, 2);
}

Output

 15
 13
 16

Time Complexity

The time complexity of this algorithm depends on the number of recursive calls made and the size of the matrix. In the worst case, where there are no hurdles and the path explores all possible directions, the time complexity can be exponential. The complexity is O(4^(N*M)), where N is the number of rows and M is the number of columns in the matrix. However, with the presence of hurdles, the actual time complexity will be lower due to backtracking.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment