Skip to main content

Find longest path in maze

Finding the longest path in a maze involves finding the path that goes through the most number of cells in the maze without revisiting any cell. This problem is known as the Longest Path Problem and is a well-known problem in computer science.

One way to solve this problem is to use a recursive depth-first search algorithm. Starting from the entrance of the maze, we explore the maze by traversing each unvisited neighbor cell of the current cell, marking it as visited and continuing the search until we reach a dead end or the exit of the maze. We keep track of the length of the path as we explore and return the longest path found.

Alternatively, we can use dynamic programming to solve this problem. We can create a two-dimensional array to store the longest path from each cell in the maze. Starting from the entrance, we can use a recursive function to fill in this array by computing the longest path from each unvisited neighbor cell and adding 1 to the length of the current cell. We can then return the maximum value in this array as the length of the longest path.

Both of these approaches require traversing the entire maze, so the time complexity is O(n^2) where n is the size of the maze.

Program Solution

// C program  
// Find longest path in maze 
#include <stdio.h>

#define ROW 4
#define COL 9
//Print grid elements
void printPath(int grid[ROW][COL])
{
	int i = 0;
	int j = 0;
	for (i = 0; i < ROW; ++i)
	{
		for (j = 0; j < COL; ++j)
		{
			printf(" %d\t", grid[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
// Copy visitor element to output collection
void copyResult(int visitor[ROW][COL], int output[ROW][COL])
{
	int i = 0;
	int j = 0;
	for (i = 0; i < ROW; ++i)
	{
		for (j = 0; j < COL; ++j)
		{
			// Assign element
			output[i][j] = visitor[i][j];
		}
	}
}
// Find all paths which is exist in given source to destination position
// r and c is Source point
// x and y is destination point 
void findPath(int collection[ROW][COL], int visitor[ROW][COL], int output[ROW][COL], int r, int c, int x, int y, int *length, int counter)
{
	if (r < 0 || r >= ROW || c < 0 || c >= COL)
	{
		//When not valid position
		return ;
	}
	else if (r == x && c == y)
	{
		//When we get destination position
		if (visitor[r][c] == 0 && *length < counter)
		{
			*length = counter;
			copyResult(visitor, output);
			//When destination are active element
			output[r][c] = counter + 1;
		}
	}
	if (visitor[r][c] != 0)
	{
		//When the element has been already been visited
		return ;
	}
	if (collection[r][c] == 1)
	{
		//Active visiting node
		visitor[r][c] = counter + 1;
		//Test four possible direction
		findPath(collection, visitor, output, r + 1, c, x, y, length, counter + 1);
		findPath(collection, visitor, output, r, c + 1, x, y, length, counter + 1);
		findPath(collection, visitor, output, r - 1, c, x, y, length, counter + 1);
		findPath(collection, visitor, output, r, c - 1, x, y, length, counter + 1);
		// Deactivate visited node status
		visitor[r][c] = 0;
	}
}
//Handles the request to find maze solution
// r and c is Source point
// x and y is destination point 
void longestPath(int collection[ROW][COL], int r, int c, int x, int y)
{
	// x and y destination point
	if (x < 0 || x >= ROW || y < 0 || y >= COL)
	{
		return;
	}
	if (r < 0 || r >= ROW || c < 0 || c >= COL)
	{
		// r and c Source point
		return;
	}
	else if (collection[r][c] == 0)
	{
		printf("\n Source are not active \n");
	}
	else if (collection[x][y] == 0)
	{
		printf("\n Destination are not active \n");
	}
	//Create resultant grid
	int output[ROW][COL];
	int visitor[ROW][COL];
	int i = 0;
	int j = 0;
	int length = -1;
	//Set initial values
	for (i = 0; i < ROW; ++i)
	{
		for (j = 0; j < COL; ++j)
		{
			output[i][j] = 0;
			visitor[i][j] = 0;
		}
	}
	findPath(collection, visitor, output, r, c, x, y, & length, 0);
	if (length != -1)
	{
		//When result are exist
		printf("\n Source point (%d,%d) Destination point (%d,%d) ", r, c, x, y);
		// Display output solution
		printf("\n Longest Path \n");
		printPath(output);
	}
	else
	{
		//When no solution possible
		printf("\n No Result \n");
	}
}
int main()
{
	int collection[ROW][COL] = 
    { 
        { 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
        { 1, 0, 1, 1, 1, 0, 1, 0, 1}, 
        { 1, 1, 1, 1, 1, 1, 1, 1, 1},
        { 0, 1, 1, 0, 0, 1, 1, 1, 1}
    }; 
	// Print input problem
	printf("\n Input Maze \n");
	printPath(collection);
	longestPath(collection, 0, 0, 3, 6);
	longestPath(collection, 1, 3, 1, 4);
	return 0;
}

Output

 Input Maze
 1	 1	 1	 1	 1	 1	 1	 1	 1
 1	 0	 1	 1	 1	 0	 1	 0	 1
 1	 1	 1	 1	 1	 1	 1	 1	 1
 0	 1	 1	 0	 0	 1	 1	 1	 1


 Source point (0,0) Destination point (3,6)
 Longest Path
 1	 0	 13	 14	 15	 16	 17	 18	 19
 2	 0	 12	 11	 10	 0	 0	 0	 20
 3	 4	 7	 8	 9	 26	 25	 24	 21
 0	 5	 6	 0	 0	 27	 28	 23	 22


 Source point (1,3) Destination point (1,4)
 Longest Path
 9	 10	 11	 12	 13	 14	 15	 16	 17
 8	 0	 0	 1	 28	 0	 0	 0	 18
 7	 6	 3	 2	 27	 26	 23	 22	 19
 0	 5	 4	 0	 0	 25	 24	 21	 20

/*
  Java Program for
  Find longest path in maze 
*/

class Maze 
{
  	public int length;
    public Maze()
  	{
    	this.length = -1;
    }
    // Print grid elements
    public void printPath(int[][] grid, int row,int col)
    {
        // Loop controlling variables
        int i = 0;
        int j = 0;

        for (i = 0; i < row; ++i)
        {
            for (j = 0; j < col; ++j)
            {
                System.out.print(" " + grid[i][j] + "\t");
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }
    // Copy visitor element to output collection
    public void copyResult(int[][] visitor, int[][] output,int row,int col)
    {
        // Loop controlling variables
        int i = 0;
        int j = 0;
        for (i = 0; i < row; ++i)
        {
            for (j = 0; j < col; ++j)
            {
                // Assign element
                output[i][j] = visitor[i][j];
            }
        }
    }
    // Find all paths which is exist in given source to destination position
    // r and c is Source point
    // x and y is destination point 
    public void findPath(int[][] collection, int[][] visitor, int[][] output, int r, int c, int x, int y, int counter,int row,int col)
    {
        if (r < 0 || r >= row || c < 0 || c >= col)
        {
            //When not valid position
            return ;
        }
        else if (r == x && c == y)
        {
            //When we get destination position
            if (visitor[r][c] == 0 && this.length < counter)
            {
                this.length = counter;
                copyResult(visitor, output, row,col);
                //When destination are active element
                output[r][c] = counter + 1;
            }
        }
        if (visitor[r][c] != 0)
        {
            //When the element has been already been visited
            return ;
        }
        if (collection[r][c] == 1)
        {
            //Active visiting node
            visitor[r][c] = counter + 1;
            //Test four possible direction
            findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row,col);
            findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row,col);
            findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row,col);
            findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row,col);
            // Deactivate visited node status
            visitor[r][c] = 0;
        }
    }
    //Handles the request to find maze solution
    // r and c is Source point
    // x and y is destination point 
    public void longestPath(int[][] collection, int r, int c, int x, int y,int row,int col)
    {


        // x and y destination point
        if (x < 0 || x >= row || y < 0 || y >= col)
        {
            return;
        }
        if (r < 0 || r >= row || c < 0 || c >= col)
        {
            // r and c Source point
            return;
        }
        else if (collection[r][c] == 0)
        {
            System.out.print("\n Source are not active \n");
        }
        else if (collection[x][y] == 0)
        {
            System.out.print("\n Destination are not active \n");
        }
        //Create resultant grid
        int[][] output  = new int[row][col];
        int[][] visitor = new int[row][col];
        int i = 0;
        int j = 0;
        this.length = -1;
        //Set initial values
        for (i = 0; i < row; ++i)
        {
            for (j = 0; j < col; ++j)
            {
                output[i][j]  = 0;
                visitor[i][j] = 0;
            }
        }
        findPath(collection, visitor, output, r, c, x, y, 0,row,col);
        if (length != -1)
        {
            //When result are exist
            System.out.print("\n Source point (" + r + "," + c + ") Destination point (" + x + "," + y + ") ");
            // Display output solution
            System.out.print("\n Longest Path \n");
            printPath(output,row,col);
        }
        else
        {
            //When no solution possible
            System.out.print("\n No Result \n");
        }
    }
    public static void main(String[] args) 
    {
        Maze task = new Maze();


        int [][]collection = 
        { 
            { 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
            { 1, 0, 1, 1, 1, 0, 1, 0, 1}, 
            { 1, 1, 1, 1, 1, 1, 1, 1, 1} ,
            { 0, 1, 1, 0, 0, 1, 1, 1, 1} ,
        }; 
        // Get size
        int row = collection.length;
        int col = collection[0].length;
        // Print input problem
        System.out.print("\n Input Maze \n");
        task.printPath(collection,row,col);
        task.longestPath(collection, 0, 0, 3, 6,row,col); 
        task.longestPath(collection, 1, 3, 1, 4,row,col); 
    }
}

Output

 Input Maze
 1	 1	 1	 1	 1	 1	 1	 1	 1
 1	 0	 1	 1	 1	 0	 1	 0	 1
 1	 1	 1	 1	 1	 1	 1	 1	 1
 0	 1	 1	 0	 0	 1	 1	 1	 1


 Source point (0,0) Destination point (3,6)
 Longest Path
 1	 0	 13	 14	 15	 16	 17	 18	 19
 2	 0	 12	 11	 10	 0	 0	 0	 20
 3	 4	 7	 8	 9	 26	 25	 24	 21
 0	 5	 6	 0	 0	 27	 28	 23	 22


 Source point (1,3) Destination point (1,4)
 Longest Path
 9	 10	 11	 12	 13	 14	 15	 16	 17
 8	 0	 0	 1	 28	 0	 0	 0	 18
 7	 6	 3	 2	 27	 26	 23	 22	 19
 0	 5	 4	 0	 0	 25	 24	 21	 20

// Include header file
#include <iostream>
#define ROW 4
#define COL 9
using namespace std;
/*
  C++ Program for
  Find longest path in maze 
*/
class Maze
{
	public: int length;
	Maze()
	{
		this->length = -1;
	}
	// Print grid elements
	void printPath(int grid[ROW][COL])
	{
		// Loop controlling variables
		int i = 0;
		int j = 0;
		for (i = 0; i < ROW; ++i)
		{
			for (j = 0; j < COL; ++j)
			{
				cout << " " << grid[i][j] << "\t";
			}
			cout << "\n";
		}
		cout << "\n";
	}
	// Copy visitor element to output collection
	void copyResult(int visitor[ROW][COL], int output[ROW][COL])
	{
		// Loop controlling variables
		int i = 0;
		int j = 0;
		for (i = 0; i < ROW; ++i)
		{
			for (j = 0; j < COL; ++j)
			{
				// Assign element
				output[i][j] = visitor[i][j];
			}
		}
	}
	// Find all paths which is exist in given source to destination position
	// r and c is Source point
	// x and y is destination point
	void findPath(int collection[ROW][COL], int visitor[ROW][COL], int output[ROW][COL], int r, int c, int x, int y, int counter)
	{
		if (r < 0 || r >= ROW || c < 0 || c >= COL)
		{
			//When not valid position
			return ;
		}
		else if (r == x && c == y)
		{
			//When we get destination position
			if (visitor[r][c] == 0 && this->length < counter)
			{
				this->length = counter;
				this->copyResult(visitor, output);
				//When destination are active element
				output[r][c] = counter + 1;
			}
		}
		if (visitor[r][c] != 0)
		{
			//When the element has been already been visited
			return ;
		}
		if (collection[r][c] == 1)
		{
			//Active visiting node
			visitor[r][c] = counter + 1;
			//Test four possible direction
			this->findPath(collection, visitor, output, r + 1, c, x, y, counter + 1);
			this->findPath(collection, visitor, output, r, c + 1, x, y, counter + 1);
			this->findPath(collection, visitor, output, r - 1, c, x, y, counter + 1);
			this->findPath(collection, visitor, output, r, c - 1, x, y, counter + 1);
			// Deactivate visited node status
			visitor[r][c] = 0;
		}
		
	}
	//Handles the request to find maze solution
	// r and c is Source point
	// x and y is destination point
	void longestPath(int collection[ROW][COL], int r, int c, int x, int y)
	{
		// x and y destination point
		if (x < 0 || x >= ROW || y < 0 || y >= COL)
		{
			return;
		}
		// r and c Source point
		if (r < 0 || r >= ROW || c < 0 || c >= COL)
		{
			return;
		}
		else if (collection[r][c] == 0)
		{
			cout << "\n Source are not active \n";
		}
		else if (collection[x][y] == 0)
		{
			cout << "\n Destination are not active \n";
		}
		//Create resultant grid
		int output[ROW][COL];
		int visitor[ROW][COL];
		int i = 0;
		int j = 0;
		this->length = -1;
		//Set initial values
		for (i = 0; i < ROW; ++i)
		{
			for (j = 0; j < COL; ++j)
			{
				output[i][j] = 0;
				visitor[i][j] = 0;
			}
		}
		this->findPath(collection, visitor, output, r, c, x, y, 0);
		if (this->length != -1)
		{
			//When result are exist
			cout << "\n Source point (" << r << "," << c << ") Destination point (" << x << "," << y << ") ";
			// Display output solution
			cout << "\n Longest Path \n";
			this->printPath(output);
		}
		else
		{
			//When no solution possible
			cout << "\n No Result \n";
		}
	}
};
int main()
{
	Maze task = Maze();
	int collection[ROW][COL] = 
    { 
        { 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
        { 1, 0, 1, 1, 1, 0, 1, 0, 1}, 
        { 1, 1, 1, 1, 1, 1, 1, 1, 1} ,
        { 0, 1, 1, 0, 0, 1, 1, 1, 1} 
    }; 

	// Print input problem
	cout << "\n Input Maze \n";
	task.printPath(collection);
	task.longestPath(collection, 0, 0, 3, 6);
	task.longestPath(collection, 1, 3, 1, 4);
	return 0;
}

Output

 Input Maze
 1	 1	 1	 1	 1	 1	 1	 1	 1
 1	 0	 1	 1	 1	 0	 1	 0	 1
 1	 1	 1	 1	 1	 1	 1	 1	 1
 0	 1	 1	 0	 0	 1	 1	 1	 1


 Source point (0,0) Destination point (3,6)
 Longest Path
 1	 0	 13	 14	 15	 16	 17	 18	 19
 2	 0	 12	 11	 10	 0	 0	 0	 20
 3	 4	 7	 8	 9	 26	 25	 24	 21
 0	 5	 6	 0	 0	 27	 28	 23	 22


 Source point (1,3) Destination point (1,4)
 Longest Path
 9	 10	 11	 12	 13	 14	 15	 16	 17
 8	 0	 0	 1	 28	 0	 0	 0	 18
 7	 6	 3	 2	 27	 26	 23	 22	 19
 0	 5	 4	 0	 0	 25	 24	 21	 20

// Include namespace system
using System;
/*
  C# Program for
  Find longest path in maze 
*/
public class Maze
{
	public int length;
	public Maze()
	{
		this.length = -1;
	}
	// Print grid elements
	public void printPath(int[,] grid, int row, int col)
	{
		// Loop controlling variables
		int i = 0;
		int j = 0;
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				Console.Write(" " + grid[i,j] + "\t");
			}
			Console.Write("\n");
		}
		Console.Write("\n");
	}
	// Copy visitor element to output collection
	public void copyResult(int[,] visitor, int[,] output, int row, int col)
	{
		// Loop controlling variables
		int i = 0;
		int j = 0;
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				// Assign element
				output[i,j] = visitor[i,j];
			}
		}
	}
	// Find all paths which is exist in given source to destination position
	// r and c is Source point
	// x and y is destination point
	public void findPath(int[,] collection, int[,] visitor, int[,] output, int r, int c, int x, int y, int counter, int row, int col)
	{
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			//When not valid position
			return ;
		}
		else if (r == x && c == y)
		{
			//When we get destination position
			if (visitor[r,c] == 0 && this.length < counter)
			{
				this.length = counter;
				copyResult(visitor, output, row, col);
				//When destination are active element
				output[r,c] = counter + 1;
			}
		}
		if (visitor[r,c] != 0)
		{
			//When the element has been already been visited
			return ;
		}
		if (collection[r,c] == 1)
		{
			//Active visiting node
			visitor[r,c] = counter + 1;
			//Test four possible direction
			findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col);
			findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col);
			findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col);
			findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col);
			// Deactivate visited node status
			visitor[r,c] = 0;
		}
	}
	//Handles the request to find maze solution
	// r and c is Source point
	// x and y is destination point
	public void longestPath(int[,] collection, int r, int c, int x, int y, int row, int col)
	{
		// x and y destination point
		if (x < 0 || x >= row || y < 0 || y >= col)
		{
			return;
		}
		// r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		else if (collection[r,c] == 0)
		{
			Console.Write("\n Source are not active \n");
		}
		else if (collection[x,y] == 0)
		{
			Console.Write("\n Destination are not active \n");
		}
		//Create resultant grid
		int[,] output = new int[row,col];
		int[,] visitor = new int[row,col];
		int i = 0;
		int j = 0;
		this.length = -1;
		//Set initial values
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				output[i,j] = 0;
				visitor[i,j] = 0;
			}
		}
		findPath(collection, visitor, output, r, c, x, y, 0, row, col);
		if (length != -1)
		{
			//When result are exist
			Console.Write("\n Source point (" + r + "," + c + ") Destination point (" + x + "," + y + ") ");
			// Display output solution
			Console.Write("\n Longest Path \n");
			printPath(output, row, col);
		}
		else
		{
			//When no solution possible
			Console.Write("\n No Result \n");
		}
	}
	public static void Main(String[] args)
	{
		Maze task = new Maze();
		int[,] collection = 
        { 
            { 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
            { 1, 0, 1, 1, 1, 0, 1, 0, 1}, 
            { 1, 1, 1, 1, 1, 1, 1, 1, 1},
            { 0, 1, 1, 0, 0, 1, 1, 1, 1} 
        };
		// Get size
		int row = collection.GetLength(0);
		int col = collection.GetLength(1);
		// Print input problem
		Console.Write("\n Input Maze \n");
		task.printPath(collection, row, col);
		task.longestPath(collection, 0, 0, 3, 6, row, col);
		task.longestPath(collection, 1, 3, 1, 4, row, col);
	}
}

Output

 Input Maze
 1	 1	 1	 1	 1	 1	 1	 1	 1
 1	 0	 1	 1	 1	 0	 1	 0	 1
 1	 1	 1	 1	 1	 1	 1	 1	 1
 0	 1	 1	 0	 0	 1	 1	 1	 1


 Source point (0,0) Destination point (3,6)
 Longest Path
 1	 0	 13	 14	 15	 16	 17	 18	 19
 2	 0	 12	 11	 10	 0	 0	 0	 20
 3	 4	 7	 8	 9	 26	 25	 24	 21
 0	 5	 6	 0	 0	 27	 28	 23	 22


 Source point (1,3) Destination point (1,4)
 Longest Path
 9	 10	 11	 12	 13	 14	 15	 16	 17
 8	 0	 0	 1	 28	 0	 0	 0	 18
 7	 6	 3	 2	 27	 26	 23	 22	 19
 0	 5	 4	 0	 0	 25	 24	 21	 20

<?php
/*
  Php Program for
  Find longest path in maze 
*/
class Maze
{
	public $length;

	function __construct()
	{
		$this->length = -1;
	}
	// Print grid elements
	public	function printPath( & $grid, $row, $col)
	{
		// Loop controlling variables
		$i = 0;
		$j = 0;
		for ($i = 0; $i < $row; ++$i)
		{
			for ($j = 0; $j < $col; ++$j)
			{
				echo " ". $grid[$i][$j] ."\t";
			}
			echo "\n";
		}
		echo "\n";
	}
	// Copy visitor element to output collection
	public	function copyResult( & $visitor, & $output, $row, $col)
	{
		// Loop controlling variables
		$i = 0;
		$j = 0;
		for ($i = 0; $i < $row; ++$i)
		{
			for ($j = 0; $j < $col; ++$j)
			{
				// Assign element
				$output[$i][$j] = $visitor[$i][$j];
			}
		}
	}
	// Find all paths which is exist in given source to destination position
	// r and c is Source point
	// x and y is destination point
	public	function findPath( & $collection, & $visitor, & $output, $r, $c, $x, $y, $counter, $row, $col)
	{
		if ($r < 0 || $r >= $row || $c < 0 || $c >= $col)
		{
			//When not valid position
			return ;
		}
		else if ($r == $x && $c == $y)
		{
			//When we get destination position
			if ($visitor[$r][$c] == 0 && $this->length < $counter)
			{
				$this->length = $counter;
				$this->copyResult($visitor, $output, $row, $col);
				//When destination are active element
				$output[$r][$c] = $counter + 1;
			}
		}
		if ($visitor[$r][$c] != 0)
		{
			//When the element has been already been visited
			return ;
		}
		if ($collection[$r][$c] == 1)
		{
			//Active visiting node
			$visitor[$r][$c] = $counter + 1;
			//Test four possible direction
			$this->findPath($collection, $visitor, $output, $r + 1, $c, $x, $y, $counter + 1, $row, $col);
			$this->findPath($collection, $visitor, $output, $r, $c + 1, $x, $y, $counter + 1, $row, $col);
			$this->findPath($collection, $visitor, $output, $r - 1, $c, $x, $y, $counter + 1, $row, $col);
			$this->findPath($collection, $visitor, $output, $r, $c - 1, $x, $y, $counter + 1, $row, $col);
			// Deactivate visited node status
			$visitor[$r][$c] = 0;
		}
	}
	//Handles the request to find maze solution
	// r and c is Source point
	// x and y is destination point
	public	function longestPath( & $collection, $r, $c, $x, $y, $row, $col)
	{
		// x and y destination point
		if ($x < 0 || $x >= $row || $y < 0 || $y >= $col)
		{
			return;
		}
		// r and c Source point
		if ($r < 0 || $r >= $row || $c < 0 || $c >= $col)
		{
			return;
		}
		else if ($collection[$r][$c] == 0)
		{
			echo "\n Source are not active \n";
		}
		else if ($collection[$x][$y] == 0)
		{
			echo "\n Destination are not active \n";
		}
		//Create resultant grid
		$output = array_fill(0, $row, array_fill(0, $col, 0));
		$visitor = array_fill(0, $row, array_fill(0, $col, 0));
		$this->length = -1;
		$this->findPath($collection, $visitor, $output, $r, $c, $x, $y, 0, $row, $col);
		if ($this->length != -1)
		{
			//When result are exist
			echo "\n Source point (". $r .",". $c .") Destination point (". $x .",". $y .") ";
			// Display output solution
			echo "\n Longest Path \n";
			$this->printPath($output, $row, $col);
		}
		else
		{
			//When no solution possible
			echo "\n No Result \n";
		}
	}
}

function main()
{
	$task = new Maze();
	$collection = array(
      array(1, 1, 1, 1, 1, 1, 1, 1, 1), 
      array(1, 0, 1, 1, 1, 0, 1, 0, 1), 
      array(1, 1, 1, 1, 1, 1, 1, 1, 1), 
      array(0, 1, 1, 0, 0, 1, 1, 1, 1)
    );
	// Get size
	$row = count($collection);
	$col = count($collection[0]);
	// Print input problem
	echo "\n Input Maze \n";
	$task->printPath($collection, $row, $col);
	$task->longestPath($collection, 0, 0, 3, 6, $row, $col);
	$task->longestPath($collection, 1, 3, 1, 4, $row, $col);
}
main();

Output

 Input Maze
 1	 1	 1	 1	 1	 1	 1	 1	 1
 1	 0	 1	 1	 1	 0	 1	 0	 1
 1	 1	 1	 1	 1	 1	 1	 1	 1
 0	 1	 1	 0	 0	 1	 1	 1	 1


 Source point (0,0) Destination point (3,6)
 Longest Path
 1	 0	 13	 14	 15	 16	 17	 18	 19
 2	 0	 12	 11	 10	 0	 0	 0	 20
 3	 4	 7	 8	 9	 26	 25	 24	 21
 0	 5	 6	 0	 0	 27	 28	 23	 22


 Source point (1,3) Destination point (1,4)
 Longest Path
 9	 10	 11	 12	 13	 14	 15	 16	 17
 8	 0	 0	 1	 28	 0	 0	 0	 18
 7	 6	 3	 2	 27	 26	 23	 22	 19
 0	 5	 4	 0	 0	 25	 24	 21	 20

/*
  Node Js Program for
  Find longest path in maze 
*/
class Maze
{
	constructor()
	{
		this.length = -1;
	}
	// Print grid elements
	printPath(grid, row, col)
	{
		// Loop controlling variables
		var i = 0;
		var j = 0;
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				process.stdout.write(" " + grid[i][j] + "\t");
			}
			process.stdout.write("\n");
		}
		process.stdout.write("\n");
	}
	// Copy visitor element to output collection
	copyResult(visitor, output, row, col)
	{
		// Loop controlling variables
		var i = 0;
		var j = 0;
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				// Assign element
				output[i][j] = visitor[i][j];
			}
		}
	}
	// Find all paths which is exist in given source to destination position
	// r and c is Source point
	// x and y is destination point
	findPath(collection, visitor, output, r, c, x, y, counter, row, col)
	{
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			//When not valid position
			return ;
		}
		else if (r == x && c == y)
		{
			//When we get destination position
			if (visitor[r][c] == 0 && this.length < counter)
			{
				this.length = counter;
				this.copyResult(visitor, output, row, col);
				//When destination are active element
				output[r][c] = counter + 1;
			}
		}
		if (visitor[r][c] != 0)
		{
			//When the element has been already been visited
			return ;
		}
		if (collection[r][c] == 1)
		{
			//Active visiting node
			visitor[r][c] = counter + 1;
			//Test four possible direction
			this.findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col);
			this.findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col);
			this.findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col);
			this.findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col);
			// Deactivate visited node status
			visitor[r][c] = 0;
		}
	}
	//Handles the request to find maze solution
	// r and c is Source point
	// x and y is destination point
	longestPath(collection, r, c, x, y, row, col)
	{
		// x and y destination point
		if (x < 0 || x >= row || y < 0 || y >= col)
		{
			return;
		}
		// r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		else if (collection[r][c] == 0)
		{
			process.stdout.write("\n Source are not active \n");
		}
		else if (collection[x][y] == 0)
		{
			process.stdout.write("\n Destination are not active \n");
		}
		//Create resultant grid
		var output = Array(row).fill(0).map(() => new Array(col).fill(0));
		var visitor = Array(row).fill(0).map(() => new Array(col).fill(0));
		this.length = -1;
		this.findPath(collection, visitor, output, r, c, x, y, 0, row, col);
		if (this.length != -1)
		{
			//When result are exist
			process.stdout.write("\n Source point (" + r + "," + c + ") Destination point (" + x + "," + y + ") ");
			// Display output solution
			process.stdout.write("\n Longest Path \n");
			this.printPath(output, row, col);
		}
		else
		{
			//When no solution possible
			process.stdout.write("\n No Result \n");
		}
	}
}

function main()
{
	var task = new Maze();
	var collection = [
		[1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 0, 1, 1, 1, 0, 1, 0, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [0, 1, 1, 0, 0, 1, 1, 1, 1]
	];
	// Get size
	var row = collection.length;
	var col = collection[0].length;
	// Print input problem
	process.stdout.write("\n Input Maze \n");
	task.printPath(collection, row, col);
	task.longestPath(collection, 0, 0, 3, 6, row, col);
	task.longestPath(collection, 1, 3, 1, 4, row, col);
}
main();

Output

 Input Maze
 1	 1	 1	 1	 1	 1	 1	 1	 1
 1	 0	 1	 1	 1	 0	 1	 0	 1
 1	 1	 1	 1	 1	 1	 1	 1	 1
 0	 1	 1	 0	 0	 1	 1	 1	 1


 Source point (0,0) Destination point (3,6)
 Longest Path
 1	 0	 13	 14	 15	 16	 17	 18	 19
 2	 0	 12	 11	 10	 0	 0	 0	 20
 3	 4	 7	 8	 9	 26	 25	 24	 21
 0	 5	 6	 0	 0	 27	 28	 23	 22


 Source point (1,3) Destination point (1,4)
 Longest Path
 9	 10	 11	 12	 13	 14	 15	 16	 17
 8	 0	 0	 1	 28	 0	 0	 0	 18
 7	 6	 3	 2	 27	 26	 23	 22	 19
 0	 5	 4	 0	 0	 25	 24	 21	 20

#   Python 3 Program for
#   Find longest path in maze 

class Maze :
	
	def __init__(self) :
		self.length = -1
	
	#  Print grid elements
	def printPath(self, grid, row, col) :
		#  Loop controlling variables
		i = 0
		j = 0
		while (i < row) :
			j = 0
			while (j < col) :
				print("", grid[i][j] ,end = "\t")
				j += 1
			
			print(end = "\n")
			i += 1
		
		print(end = "\n")
	
	#  Copy visitor element to output collection
	def copyResult(self, visitor, output, row, col) :
		#  Loop controlling variables
		i = 0
		j = 0
		while (i < row) :
			j = 0
			while (j < col) :
				#  Assign element
				output[i][j] = visitor[i][j]
				j += 1
			
			i += 1
		
	
	#  Find all paths which is exist in given source to destination position
	#  r and c is Source point
	#  x and y is destination point
	def findPath(self, collection, visitor, output, r, c, x, y, counter, row, col) :
		if (r < 0 or r >= row or c < 0 or c >= col) :
			# When not valid position
			return 
		
		elif(r == x and c == y) :
			# When we get destination position
			if (visitor[r][c] == 0 and self.length < counter) :
				self.length = counter
				self.copyResult(visitor, output, row, col)
				# When destination are active element
				output[r][c] = counter + 1
			
		
		if (visitor[r][c] != 0) :
			# When the element has been already been visited
			return 
		
		if (collection[r][c] == 1) :
			# Active visiting node
			visitor[r][c] = counter + 1
			# Test four possible direction
			self.findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col)
			self.findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col)
			self.findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col)
			self.findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col)
			#  Deactivate visited node status
			visitor[r][c] = 0

	
	# Handles the request to find maze solution
	#  r and c is Source point
	#  x and y is destination point
	def longestPath(self, collection, r, c, x, y, row, col) :
		#  x and y destination point
		if (x < 0 or x >= row or y < 0 or y >= col) :
			return
		
		#  r and c Source point
		if (r < 0 or r >= row or c < 0 or c >= col) :
			return
		
		elif(collection[r][c] == 0) :
			print("\n Source are not active ")
		
		elif(collection[x][y] == 0) :
			print("\n Destination are not active ")
		
		# Create resultant grid
		output = [[0] * (col) for _ in range(row) ]
		visitor = [[0] * (col) for _ in range(row) ]
		self.length = -1
		self.findPath(collection, visitor, output, r, c, x, y, 0, row, col)
		if (self.length != -1) :
			# When result are exist
			print("\n Source point (", r ,",", c ,") Destination point (", x ,",", y ,") ", end = "")
			#  Display output solution
			print("\n Longest Path ")
			self.printPath(output, row, col)
		else :
			# When no solution possible
			print("\n No Result ")
		
	

def main() :
	task = Maze()
	collection = [
	  [1, 1, 1, 1, 1, 1, 1, 1, 1] , 
      [1, 0, 1, 1, 1, 0, 1, 0, 1] , 
      [1, 1, 1, 1, 1, 1, 1, 1, 1] , 
      [0, 1, 1, 0, 0, 1, 1, 1, 1]
	]
	#  Get size
	row = len(collection)
	col = len(collection[0])
	#  Print input problem
	print("\n Input Maze ")
	task.printPath(collection, row, col)
	task.longestPath(collection, 0, 0, 3, 6, row, col)
	task.longestPath(collection, 1, 3, 1, 4, row, col)

if __name__ == "__main__": main()

Output

 Input Maze
 1	 1	 1	 1	 1	 1	 1	 1	 1
 1	 0	 1	 1	 1	 0	 1	 0	 1
 1	 1	 1	 1	 1	 1	 1	 1	 1
 0	 1	 1	 0	 0	 1	 1	 1	 1


 Source point ( 0 , 0 ) Destination point ( 3 , 6 )
 Longest Path
 1	 0	 13	 14	 15	 16	 17	 18	 19
 2	 0	 12	 11	 10	 0	 0	 0	 20
 3	 4	 7	 8	 9	 26	 25	 24	 21
 0	 5	 6	 0	 0	 27	 28	 23	 22


 Source point ( 1 , 3 ) Destination point ( 1 , 4 )
 Longest Path
 9	 10	 11	 12	 13	 14	 15	 16	 17
 8	 0	 0	 1	 28	 0	 0	 0	 18
 7	 6	 3	 2	 27	 26	 23	 22	 19
 0	 5	 4	 0	 0	 25	 24	 21	 20

#   Ruby Program for
#   Find longest path in maze 

class Maze  
	# Define the accessor and reader of class Maze  
	attr_reader :length
	attr_accessor :length
 
	
	def initialize() 
		self.length = -1
	end

	#  Print grid elements
	def printPath(grid, row, col) 
		#  Loop controlling variables
		i = 0
		j = 0
		while (i < row) 
			j = 0
			while (j < col) 
				print(" ", grid[i][j] ,"\t")
				j += 1
			end

			print("\n")
			i += 1
		end

		print("\n")
	end

	#  Copy visitor element to output collection
	def copyResult(visitor, output, row, col) 
		#  Loop controlling variables
		i = 0
		j = 0
		while (i < row) 
			j = 0
			while (j < col) 
				#  Assign element
				output[i][j] = visitor[i][j]
				j += 1
			end

			i += 1
		end

	end

	#  Find all paths which is exist in given source to destination position
	#  r and c is Source point
	#  x and y is destination point
	def findPath(collection, visitor, output, r, c, x, y, counter, row, col) 
		if (r < 0 || r >= row || c < 0 || c >= col) 
			# When not valid position
			return 
		elsif(r == x && c == y) 
			# When we get destination position
			if (visitor[r][c] == 0 && self.length < counter) 
				self.length = counter
				self.copyResult(visitor, output, row, col)
				# When destination are active element
				output[r][c] = counter + 1
			end

		end

		if (visitor[r][c] != 0) 
			# When the element has been already been visited
			return 
		end

		if (collection[r][c] == 1) 
			# Active visiting node
			visitor[r][c] = counter + 1
			# Test four possible direction
			self.findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col)
			self.findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col)
			self.findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col)
			self.findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col)
			#  Deactivate visited node status
			visitor[r][c] = 0
		end
	end

	# Handles the request to find maze solution
	#  r and c is Source point
	#  x and y is destination point
	def longestPath(collection, r, c, x, y, row, col) 
		#  x and y destination point
		if (x < 0 || x >= row || y < 0 || y >= col) 
			return
		end

		#  r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col) 
			return
		elsif(collection[r][c] == 0) 
			print("\n Source are not active \n")
		elsif(collection[x][y] == 0) 
			print("\n Destination are not active \n")
		end

		# Create resultant grid
		output = Array.new(row) {Array.new(col) {0}}
		visitor = Array.new(row) {Array.new(col) {0}}
		self.length = -1
		self.findPath(collection, visitor, output, r, c, x, y, 0, row, col)
		if (length != -1) 
			# When result are exist
			print("\n Source point (", r ,",", c ,") Destination point (", x ,",", y ,") ")
			#  Display output solution
			print("\n Longest Path \n")
			self.printPath(output, row, col)
		else 
			# When no solution possible
			print("\n No Result \n")
		end

	end

end

def main() 
	task = Maze.new()
	collection = [
	  [1, 1, 1, 1, 1, 1, 1, 1, 1] , 
      [1, 0, 1, 1, 1, 0, 1, 0, 1] , 
      [1, 1, 1, 1, 1, 1, 1, 1, 1] , 
      [0, 1, 1, 0, 0, 1, 1, 1, 1]
	]
	#  Get size
	row = collection.length
	col = collection[0].length
	#  Print input problem
	print("\n Input Maze \n")
	task.printPath(collection, row, col)
	task.longestPath(collection, 0, 0, 3, 6, row, col)
	task.longestPath(collection, 1, 3, 1, 4, row, col)
end

main()

Output

 Input Maze 
 1	 1	 1	 1	 1	 1	 1	 1	 1	
 1	 0	 1	 1	 1	 0	 1	 0	 1	
 1	 1	 1	 1	 1	 1	 1	 1	 1	
 0	 1	 1	 0	 0	 1	 1	 1	 1	


 Source point (0,0) Destination point (3,6) 
 Longest Path 
 1	 0	 13	 14	 15	 16	 17	 18	 19	
 2	 0	 12	 11	 10	 0	 0	 0	 20	
 3	 4	 7	 8	 9	 26	 25	 24	 21	
 0	 5	 6	 0	 0	 27	 28	 23	 22	


 Source point (1,3) Destination point (1,4) 
 Longest Path 
 9	 10	 11	 12	 13	 14	 15	 16	 17	
 8	 0	 0	 1	 28	 0	 0	 0	 18	
 7	 6	 3	 2	 27	 26	 23	 22	 19	
 0	 5	 4	 0	 0	 25	 24	 21	 20	


/*
  Scala Program for
  Find longest path in maze 
*/
class Maze(var length: Int)
{
	def this()
	{
		this(-1);
	}
	// Print grid elements
	def printPath(grid: Array[Array[Int]], row: Int, col: Int): Unit = {
		// Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				print(" " + grid(i)(j) + "\t");
				j += 1;
			}
			print("\n");
			i += 1;
		}
		print("\n");
	}
	// Copy visitor element to output collection
	def copyResult(visitor: Array[Array[Int]], output: Array[Array[Int]], row: Int, col: Int): Unit = {
		// Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				// Assign element
				output(i)(j) = visitor(i)(j);
				j += 1;
			}
			i += 1;
		}
	}
	// Find all paths which is exist in given source to destination position
	// r and c is Source point
	// x and y is destination point
	def findPath(collection: Array[Array[Int]], visitor: Array[Array[Int]], output: Array[Array[Int]], r: Int, c: Int, x: Int, y: Int, counter: Int, row: Int, col: Int): Unit = {
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			//When not valid position
			return ;
		}
		else if (r == x && c == y)
		{
			//When we get destination position
			if (visitor(r)(c) == 0 && this.length < counter)
			{
				this.length = counter;
				this.copyResult(visitor, output, row, col);
				//When destination are active element
				output(r)(c) = counter + 1;
			}
		}
		if (visitor(r)(c) != 0)
		{
			//When the element has been already been visited
			return ;
		}
		if (collection(r)(c) == 1)
		{
			//Active visiting node
			visitor(r)(c) = counter + 1;
			//Test four possible direction
			this.findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col);
			this.findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col);
			this.findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col);
			this.findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col);
			// Deactivate visited node status
			visitor(r)(c) = 0;
		}
	}
	//Handles the request to find maze solution
	// r and c is Source point
	// x and y is destination point
	def longestPath(collection: Array[Array[Int]], r: Int, c: Int, x: Int, y: Int, row: Int, col: Int): Unit = {
		// x and y destination point
		if (x < 0 || x >= row || y < 0 || y >= col)
		{
			return;
		}
		// r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		else if (collection(r)(c) == 0)
		{
			print("\n Source are not active \n");
		}
		else if (collection(x)(y) == 0)
		{
			print("\n Destination are not active \n");
		}
		//Create resultant grid
		var output: Array[Array[Int]] = Array.fill[Int](row, col)(0);
		var visitor: Array[Array[Int]] = Array.fill[Int](row, col)(0);
		this.length = -1;
		this.findPath(collection, visitor, output, r, c, x, y, 0, row, col);
		if (length != -1)
		{
			//When result are exist
			print("\n Source point (" + r + "," + c + ") Destination point (" + x + "," + y + ") ");
			// Display output solution
			print("\n Longest Path \n");
			this.printPath(output, row, col);
		}
		else
		{
			//When no solution possible
			print("\n No Result \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Maze = new Maze();
		var collection: Array[Array[Int]] = Array(
          Array(1, 1, 1, 1, 1, 1, 1, 1, 1), 
          Array(1, 0, 1, 1, 1, 0, 1, 0, 1), 
          Array(1, 1, 1, 1, 1, 1, 1, 1, 1), 
          Array(0, 1, 1, 0, 0, 1, 1, 1, 1)
        );
		// Get size
		var row: Int = collection.length;
		var col: Int = collection(0).length;
		// Print input problem
		print("\n Input Maze \n");
		task.printPath(collection, row, col);
		task.longestPath(collection, 0, 0, 3, 6, row, col);
		task.longestPath(collection, 1, 3, 1, 4, row, col);
	}
}

Output

 Input Maze
 1	 1	 1	 1	 1	 1	 1	 1	 1
 1	 0	 1	 1	 1	 0	 1	 0	 1
 1	 1	 1	 1	 1	 1	 1	 1	 1
 0	 1	 1	 0	 0	 1	 1	 1	 1


 Source point (0,0) Destination point (3,6)
 Longest Path
 1	 0	 13	 14	 15	 16	 17	 18	 19
 2	 0	 12	 11	 10	 0	 0	 0	 20
 3	 4	 7	 8	 9	 26	 25	 24	 21
 0	 5	 6	 0	 0	 27	 28	 23	 22


 Source point (1,3) Destination point (1,4)
 Longest Path
 9	 10	 11	 12	 13	 14	 15	 16	 17
 8	 0	 0	 1	 28	 0	 0	 0	 18
 7	 6	 3	 2	 27	 26	 23	 22	 19
 0	 5	 4	 0	 0	 25	 24	 21	 20

/*
  Swift 4 Program for
  Find longest path in maze 
*/
class Maze
{
	var length: Int;
	init()
	{
		self.length = -1;
	}
	// Print grid elements
	func printPath(_ grid: [[Int]], _ row: Int, _ col: Int)
	{
		// Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				print("", grid[i][j], terminator: "\t");
				j += 1;
			}
			print(terminator: "\n");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Copy visitor element to output collection
	func copyResult(_ visitor: [[Int]], _ output: inout[[Int]], _ row: Int, _ col: Int)
	{
		// Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				// Assign element
				output[i][j] = visitor[i][j];
				j += 1;
			}
			i += 1;
		}
	}
	// Find all paths which is exist in given source to destination position
	// r and c is Source point
	// x and y is destination point
	func findPath(_ collection: [[Int]], _ visitor: inout[[Int]], _ output: inout[[Int]], _ r: Int, _ c: Int, _ x: Int, _ y: Int, _ counter: Int, _ row: Int, _ col: Int)
	{
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			//When not valid position
			return;
		}
		else if (r == x && c == y)
		{
			//When we get destination position
			if (visitor[r][c] == 0 && self.length < counter)
			{
				self.length = counter;
				self.copyResult(visitor, &output, row, col);
				//When destination are active element
				output[r][c] = counter + 1;
			}
		}
		if (visitor[r][c]  != 0)
		{
			//When the element has been already been visited
			return;
		}
		if (collection[r][c] == 1)
		{
			//Active visiting node
			visitor[r][c] = counter + 1;
			//Test four possible direction
			self.findPath(collection, &visitor, &output, r + 1, c, x, y, counter + 1, row, col);
			self.findPath(collection, &visitor, &output, r, c + 1, x, y, counter + 1, row, col);
			self.findPath(collection, &visitor, &output, r - 1, c, x, y, counter + 1, row, col);
			self.findPath(collection, &visitor, &output, r, c - 1, x, y, counter + 1, row, col);
			// Deactivate visited node status
			visitor[r][c] = 0;
		}
	}
	//Handles the request to find maze solution
	// r and c is Source point
	// x and y is destination point
	func longestPath(_ collection: [[Int]], _ r: Int, _ c: Int, _ x: Int, _ y: Int, _ row: Int, _ col: Int)
	{
		// x and y destination point
		if (x < 0 || x >= row || y < 0 || y >= col)
		{
			return;
		}
		// r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		else if (collection[r][c] == 0)
		{
			print("\n Source are not active ");
		}
		else if (collection[x][y] == 0)
		{
			print("\n Destination are not active ");
		}
		//Create resultant grid
		var output: [[Int]]  = Array(repeating: Array(repeating: 0, count: col), count: row);
		var visitor: [[Int]] = Array(repeating: Array(repeating: 0, count: col), count: row);
		self.length = -1;
		self.findPath(collection, &visitor, &output, r, c, x, y, 0, row, col);
		if (self.length  != -1)
		{
			//When result are exist
			print("\n Source point (", r ,",", c ,") Destination point (", x ,",", y ,") ", terminator: "");
			// Display output solution
			print("\n Longest Path ");
			self.printPath(output, row, col);
		}
		else
		{
			//When no solution possible
			print("\n No Result ");
		}
	}
}
func main()
{
	let task: Maze = Maze();
	let collection: [[Int]] = [
		[1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 0, 1, 1, 1, 0, 1, 0, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [0, 1, 1, 0, 0, 1, 1, 1, 1]
	];
	// Get size
	let row: Int = collection.count;
	let col: Int = collection[0].count;
	// Print input problem
	print("\n Input Maze ");
	task.printPath(collection, row, col);
	task.longestPath(collection, 0, 0, 3, 6, row, col);
	task.longestPath(collection, 1, 3, 1, 4, row, col);
}
main();

Output

 Input Maze
 1	 1	 1	 1	 1	 1	 1	 1	 1
 1	 0	 1	 1	 1	 0	 1	 0	 1
 1	 1	 1	 1	 1	 1	 1	 1	 1
 0	 1	 1	 0	 0	 1	 1	 1	 1


 Source point ( 0 , 0 ) Destination point ( 3 , 6 )
 Longest Path
 1	 0	 13	 14	 15	 16	 17	 18	 19
 2	 0	 12	 11	 10	 0	 0	 0	 20
 3	 4	 7	 8	 9	 26	 25	 24	 21
 0	 5	 6	 0	 0	 27	 28	 23	 22


 Source point ( 1 , 3 ) Destination point ( 1 , 4 )
 Longest Path
 9	 10	 11	 12	 13	 14	 15	 16	 17
 8	 0	 0	 1	 28	 0	 0	 0	 18
 7	 6	 3	 2	 27	 26	 23	 22	 19
 0	 5	 4	 0	 0	 25	 24	 21	 20

/*
  Kotlin Program for
  Find longest path in maze 
*/
class Maze
{
	var length: Int;
	constructor()
	{
		this.length = -1;
	}
	// Print grid elements
	fun printPath(grid: Array<Array<Int>> , row: Int, col: Int): Unit
	{
		// Loop controlling variables
		var i: Int = 0;
		var j: Int ;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				print(" " + grid[i][j] + "\t");
				j += 1;
			}
			print("\n");
			i += 1;
		}
		print("\n");
	}
	// Copy visitor element to output collection
	fun copyResult(visitor: Array<Array<Int>> , output: Array <Array<Int>> , row: Int, col: Int): Unit
	{
		// Loop controlling variables
		var i: Int = 0;
		var j: Int ;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				// Assign element
				output[i][j] = visitor[i][j];
				j += 1;
			}
			i += 1;
		}
	}
	// Find all paths which is exist in given source to destination position
	// r and c is Source point
	// x and y is destination point
	fun findPath(collection: Array <Array <Int>> , visitor: Array <Array<Int>> , output: Array <Array<Int>> , r: Int, c: Int, x: Int, y: Int, counter: Int, row: Int, col: Int)
	{
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			//When not valid position
			return ;
		}
		else if (r == x && c == y)
		{
			//When we get destination position
			if (visitor[r][c] == 0 && this.length < counter)
			{
				this.length = counter;
				this.copyResult(visitor, output, row, col);
				//When destination are active element
				output[r][c] = counter + 1;
			}
		}
		if (visitor[r][c] != 0)
		{
			//When the element has been already been visited
			return ;
		}
		if (collection[r][c] == 1)
		{
			//Active visiting node
			visitor[r][c] = counter + 1;
			//Test four possible direction
			this.findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col);
			this.findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col);
			this.findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col);
			this.findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col);
			// Deactivate visited node status
			visitor[r][c] = 0;
		}
		
	}
	//Handles the request to find maze solution
	// r and c is Source point
	// x and y is destination point
	fun longestPath(collection: Array <Array <Int>> , r: Int, c: Int, x: Int, y: Int, row: Int, col: Int): Unit
	{
		// x and y destination point
		if (x < 0 || x >= row || y < 0 || y >= col)
		{
			return;
		}
		// r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		else if (collection[r][c] == 0)
		{
			print("\n Source are not active \n");
		}
		else if (collection[x][y] == 0)
		{
			print("\n Destination are not active \n");
		}
		//Create resultant grid
		var output: Array < Array < Int >> = Array(row)
		{
			Array(col)
			{
				0
			}
		};
		var visitor: Array < Array < Int >> = Array(row)
		{
			Array(col)
			{
				0
			}
		};
		this.length = -1;
		this.findPath(collection, visitor, output, r, c, x, y, 0, row, col);
		if (length != -1)
		{
			//When result are exist
			print("\n Source point (" + r + "," + c + ") Destination point (" + x + "," + y + ") ");
			// Display output solution
			print("\n Longest Path \n");
			this.printPath(output, row, col);
		}
		else
		{
			//When no solution possible
			print("\n No Result \n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Maze = Maze();
	var collection: Array <Array<Int>> = arrayOf(
      arrayOf(1, 1, 1, 1, 1, 1, 1, 1, 1), 
      arrayOf(1, 0, 1, 1, 1, 0, 1, 0, 1), 
      arrayOf(1, 1, 1, 1, 1, 1, 1, 1, 1), 
      arrayOf(0, 1, 1, 0, 0, 1, 1, 1, 1)
    );
	// Get size
	var row: Int = collection.count();
	var col: Int = collection[0].count();
	// Print input problem
	print("\n Input Maze \n");
	task.printPath(collection, row, col);
	task.longestPath(collection, 0, 0, 3, 6, row, col);
	task.longestPath(collection, 1, 3, 1, 4, row, col);
}

Output

 Input Maze
 1	 1	 1	 1	 1	 1	 1	 1	 1
 1	 0	 1	 1	 1	 0	 1	 0	 1
 1	 1	 1	 1	 1	 1	 1	 1	 1
 0	 1	 1	 0	 0	 1	 1	 1	 1


 Source point (0,0) Destination point (3,6)
 Longest Path
 1	 0	 13	 14	 15	 16	 17	 18	 19
 2	 0	 12	 11	 10	 0	 0	 0	 20
 3	 4	 7	 8	 9	 26	 25	 24	 21
 0	 5	 6	 0	 0	 27	 28	 23	 22


 Source point (1,3) Destination point (1,4)
 Longest Path
 9	 10	 11	 12	 13	 14	 15	 16	 17
 8	 0	 0	 1	 28	 0	 0	 0	 18
 7	 6	 3	 2	 27	 26	 23	 22	 19
 0	 5	 4	 0	 0	 25	 24	 21	 20
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