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.
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