Skip to main content

Longest possible route in a matrix with hurdles

Here given code implementation process.

// 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
Last updated on by Kalkicode




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