Posted on by Kalkicode
Code Backtracking

Find longest path in maze

In this article, we will explore how to find the longest path in a maze using a depth-first search algorithm. We'll start by explaining the problem statement and provide a suitable example to illustrate the concept. Then, we'll present the pseudocode algorithm along with a detailed explanation. Finally, we'll analyze the resultant output and discuss the time complexity of the code.

Problem Statement

Given a maze represented as a 2D grid, we need to find the longest path from a source point to a destination point. The maze consists of cells, some of which are obstacles and others are accessible. We can only move horizontally or vertically, and we cannot cross the obstacles.

Example:

Consider the following 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

We want to find the longest path from the source point (0, 0) to the destination point (3, 6).

Pseudocode Algorithm

function printPath(grid):
    for each row in grid:
        for each element in row:
            print element
        print new line

function copyResult(visitor, output):
    for each row in visitor:
        for each element in row:
            assign element to output

function findPath(collection, visitor, output, r, c, x, y, length, counter):
    if r < 0 or r >= ROW or c < 0 or c >= COL:
        return
    else if r = x and c = y:
        if visitor[r][c] = 0 and length < counter:
            length = counter
            copyResult(visitor, output)
            output[r][c] = counter + 1
    if visitor[r][c] != 0:
        return
    if collection[r][c] = 1:
        visitor[r][c] = 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)
        findPath(collection, visitor, output, r - 1, c, x, y, length, counter + 1)
        findPath(collection, visitor, output, r, c - 1, x, y, length, counter + 1)
        visitor[r][c] = 0

function longestPath(collection, r, c, x, y):
    if x < 0 or x >= ROW or y < 0 or y >= COL:
        return
    if r < 0 or r >= ROW or c < 0 or c >= COL:
        return
    else if collection[r][c] = 0:
        print "Source is not active"
    else if collection[x][y] = 0:
        print "Destination is not active"
    output[ROW][COL]
    visitor[ROW][COL]
    length = -1
    for each row in output:
        for each element in row:
            set element to 0
    for each row in visitor:
        for each element in row:
            set element to 0
    findPath(collection, visitor, output, r, c, x, y, length, 0)
    if length != -1:
        print "Source point (r, c) Destination point (x, y)"
        print "Longest Path"
        printPath(output)
    else:
        print "No Result"

Explanation

The algorithm consists of several functions:

  • printPath: This function is responsible for printing the elements of the grid.
  • copyResult: This function copies the elements of the visitor grid to the output grid.
  • findPath: This recursive function finds all possible paths from the source to the destination. It keeps track of the visited cells, the current path length, and the longest path found so far.
  • longestPath: This function handles the request to find the longest path. It initializes the output and visitor grids and calls the findPath function.

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

Resultant Output

The provided 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

For the source point (0, 0) and the destination point (3, 6), the longest path is:

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

For the source point (1, 3) and the destination point (1, 4), the longest path is:

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

Time Complexity

The time complexity of this algorithm can be analyzed as follows:

  • The printPath function has a time complexity of O(ROW * COL) since it iterates over all elements in the grid.
  • The copyResult function also has a time complexity of O(ROW * COL) since it copies the elements from the visitor grid to the output grid in a nested loop.
  • The findPath function is a recursive function that explores all possible paths from the source to the destination. It visits each cell in the grid once. In the worst case scenario, it may explore all cells in the grid, resulting in a time complexity of O(ROW * COL).
  • The longestPath function initializes the output and visitor grids, and then calls the findPath function. It also has a time complexity of O(ROW * COL).

Therefore, the overall time complexity of the algorithm is O(ROW * COL), where ROW is the number of rows in the grid and COL is the number of columns in the grid.

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