Find longest path in maze
Finding the longest path in a maze involves finding the path that goes through the most number of cells in the maze without revisiting any cell. This problem is known as the Longest Path Problem and is a well-known problem in computer science.
One way to solve this problem is to use a recursive depth-first search algorithm. Starting from the entrance of the maze, we explore the maze by traversing each unvisited neighbor cell of the current cell, marking it as visited and continuing the search until we reach a dead end or the exit of the maze. We keep track of the length of the path as we explore and return the longest path found.
Alternatively, we can use dynamic programming to solve this problem. We can create a two-dimensional array to store the longest path from each cell in the maze. Starting from the entrance, we can use a recursive function to fill in this array by computing the longest path from each unvisited neighbor cell and adding 1 to the length of the current cell. We can then return the maximum value in this array as the length of the longest path.
Both of these approaches require traversing the entire maze, so the time complexity is O(n^2) where n is the size of the maze.
Program Solution
// C program
// Find longest path in maze
#include <stdio.h>
#define ROW 4
#define COL 9
//Print grid elements
void printPath(int grid[ROW][COL])
{
int i = 0;
int j = 0;
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
printf(" %d\t", grid[i][j]);
}
printf("\n");
}
printf("\n");
}
// Copy visitor element to output collection
void copyResult(int visitor[ROW][COL], int output[ROW][COL])
{
int i = 0;
int j = 0;
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
// Assign element
output[i][j] = visitor[i][j];
}
}
}
// Find all paths which is exist in given source to destination position
// r and c is Source point
// x and y is destination point
void findPath(int collection[ROW][COL], int visitor[ROW][COL], int output[ROW][COL], int r, int c, int x, int y, int *length, int counter)
{
if (r < 0 || r >= ROW || c < 0 || c >= COL)
{
//When not valid position
return ;
}
else if (r == x && c == y)
{
//When we get destination position
if (visitor[r][c] == 0 && *length < counter)
{
*length = counter;
copyResult(visitor, output);
//When destination are active element
output[r][c] = counter + 1;
}
}
if (visitor[r][c] != 0)
{
//When the element has been already been visited
return ;
}
if (collection[r][c] == 1)
{
//Active visiting node
visitor[r][c] = counter + 1;
//Test four possible direction
findPath(collection, visitor, output, r + 1, c, x, y, length, counter + 1);
findPath(collection, visitor, output, r, c + 1, x, y, length, counter + 1);
findPath(collection, visitor, output, r - 1, c, x, y, length, counter + 1);
findPath(collection, visitor, output, r, c - 1, x, y, length, counter + 1);
// Deactivate visited node status
visitor[r][c] = 0;
}
}
//Handles the request to find maze solution
// r and c is Source point
// x and y is destination point
void longestPath(int collection[ROW][COL], int r, int c, int x, int y)
{
// x and y destination point
if (x < 0 || x >= ROW || y < 0 || y >= COL)
{
return;
}
if (r < 0 || r >= ROW || c < 0 || c >= COL)
{
// r and c Source point
return;
}
else if (collection[r][c] == 0)
{
printf("\n Source are not active \n");
}
else if (collection[x][y] == 0)
{
printf("\n Destination are not active \n");
}
//Create resultant grid
int output[ROW][COL];
int visitor[ROW][COL];
int i = 0;
int j = 0;
int length = -1;
//Set initial values
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
output[i][j] = 0;
visitor[i][j] = 0;
}
}
findPath(collection, visitor, output, r, c, x, y, & length, 0);
if (length != -1)
{
//When result are exist
printf("\n Source point (%d,%d) Destination point (%d,%d) ", r, c, x, y);
// Display output solution
printf("\n Longest Path \n");
printPath(output);
}
else
{
//When no solution possible
printf("\n No Result \n");
}
}
int main()
{
int collection[ROW][COL] =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1},
{ 1, 0, 1, 1, 1, 0, 1, 0, 1},
{ 1, 1, 1, 1, 1, 1, 1, 1, 1},
{ 0, 1, 1, 0, 0, 1, 1, 1, 1}
};
// Print input problem
printf("\n Input Maze \n");
printPath(collection);
longestPath(collection, 0, 0, 3, 6);
longestPath(collection, 1, 3, 1, 4);
return 0;
}
Output
Input Maze
1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1 1
Source point (0,0) Destination point (3,6)
Longest Path
1 0 13 14 15 16 17 18 19
2 0 12 11 10 0 0 0 20
3 4 7 8 9 26 25 24 21
0 5 6 0 0 27 28 23 22
Source point (1,3) Destination point (1,4)
Longest Path
9 10 11 12 13 14 15 16 17
8 0 0 1 28 0 0 0 18
7 6 3 2 27 26 23 22 19
0 5 4 0 0 25 24 21 20
/*
Java Program for
Find longest path in maze
*/
class Maze
{
public int length;
public Maze()
{
this.length = -1;
}
// Print grid elements
public void printPath(int[][] grid, int row,int col)
{
// Loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
System.out.print(" " + grid[i][j] + "\t");
}
System.out.print("\n");
}
System.out.print("\n");
}
// Copy visitor element to output collection
public void copyResult(int[][] visitor, int[][] output,int row,int col)
{
// Loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
// Assign element
output[i][j] = visitor[i][j];
}
}
}
// Find all paths which is exist in given source to destination position
// r and c is Source point
// x and y is destination point
public void findPath(int[][] collection, int[][] visitor, int[][] output, int r, int c, int x, int y, int counter,int row,int col)
{
if (r < 0 || r >= row || c < 0 || c >= col)
{
//When not valid position
return ;
}
else if (r == x && c == y)
{
//When we get destination position
if (visitor[r][c] == 0 && this.length < counter)
{
this.length = counter;
copyResult(visitor, output, row,col);
//When destination are active element
output[r][c] = counter + 1;
}
}
if (visitor[r][c] != 0)
{
//When the element has been already been visited
return ;
}
if (collection[r][c] == 1)
{
//Active visiting node
visitor[r][c] = counter + 1;
//Test four possible direction
findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row,col);
findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row,col);
findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row,col);
findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row,col);
// Deactivate visited node status
visitor[r][c] = 0;
}
}
//Handles the request to find maze solution
// r and c is Source point
// x and y is destination point
public void longestPath(int[][] collection, int r, int c, int x, int y,int row,int col)
{
// x and y destination point
if (x < 0 || x >= row || y < 0 || y >= col)
{
return;
}
if (r < 0 || r >= row || c < 0 || c >= col)
{
// r and c Source point
return;
}
else if (collection[r][c] == 0)
{
System.out.print("\n Source are not active \n");
}
else if (collection[x][y] == 0)
{
System.out.print("\n Destination are not active \n");
}
//Create resultant grid
int[][] output = new int[row][col];
int[][] visitor = new int[row][col];
int i = 0;
int j = 0;
this.length = -1;
//Set initial values
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
output[i][j] = 0;
visitor[i][j] = 0;
}
}
findPath(collection, visitor, output, r, c, x, y, 0,row,col);
if (length != -1)
{
//When result are exist
System.out.print("\n Source point (" + r + "," + c + ") Destination point (" + x + "," + y + ") ");
// Display output solution
System.out.print("\n Longest Path \n");
printPath(output,row,col);
}
else
{
//When no solution possible
System.out.print("\n No Result \n");
}
}
public static void main(String[] args)
{
Maze task = new Maze();
int [][]collection =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1},
{ 1, 0, 1, 1, 1, 0, 1, 0, 1},
{ 1, 1, 1, 1, 1, 1, 1, 1, 1} ,
{ 0, 1, 1, 0, 0, 1, 1, 1, 1} ,
};
// Get size
int row = collection.length;
int col = collection[0].length;
// Print input problem
System.out.print("\n Input Maze \n");
task.printPath(collection,row,col);
task.longestPath(collection, 0, 0, 3, 6,row,col);
task.longestPath(collection, 1, 3, 1, 4,row,col);
}
}
Output
Input Maze
1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1 1
Source point (0,0) Destination point (3,6)
Longest Path
1 0 13 14 15 16 17 18 19
2 0 12 11 10 0 0 0 20
3 4 7 8 9 26 25 24 21
0 5 6 0 0 27 28 23 22
Source point (1,3) Destination point (1,4)
Longest Path
9 10 11 12 13 14 15 16 17
8 0 0 1 28 0 0 0 18
7 6 3 2 27 26 23 22 19
0 5 4 0 0 25 24 21 20
// Include header file
#include <iostream>
#define ROW 4
#define COL 9
using namespace std;
/*
C++ Program for
Find longest path in maze
*/
class Maze
{
public: int length;
Maze()
{
this->length = -1;
}
// Print grid elements
void printPath(int grid[ROW][COL])
{
// Loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
cout << " " << grid[i][j] << "\t";
}
cout << "\n";
}
cout << "\n";
}
// Copy visitor element to output collection
void copyResult(int visitor[ROW][COL], int output[ROW][COL])
{
// Loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
// Assign element
output[i][j] = visitor[i][j];
}
}
}
// Find all paths which is exist in given source to destination position
// r and c is Source point
// x and y is destination point
void findPath(int collection[ROW][COL], int visitor[ROW][COL], int output[ROW][COL], int r, int c, int x, int y, int counter)
{
if (r < 0 || r >= ROW || c < 0 || c >= COL)
{
//When not valid position
return ;
}
else if (r == x && c == y)
{
//When we get destination position
if (visitor[r][c] == 0 && this->length < counter)
{
this->length = counter;
this->copyResult(visitor, output);
//When destination are active element
output[r][c] = counter + 1;
}
}
if (visitor[r][c] != 0)
{
//When the element has been already been visited
return ;
}
if (collection[r][c] == 1)
{
//Active visiting node
visitor[r][c] = counter + 1;
//Test four possible direction
this->findPath(collection, visitor, output, r + 1, c, x, y, counter + 1);
this->findPath(collection, visitor, output, r, c + 1, x, y, counter + 1);
this->findPath(collection, visitor, output, r - 1, c, x, y, counter + 1);
this->findPath(collection, visitor, output, r, c - 1, x, y, counter + 1);
// Deactivate visited node status
visitor[r][c] = 0;
}
}
//Handles the request to find maze solution
// r and c is Source point
// x and y is destination point
void longestPath(int collection[ROW][COL], int r, int c, int x, int y)
{
// x and y destination point
if (x < 0 || x >= ROW || y < 0 || y >= COL)
{
return;
}
// r and c Source point
if (r < 0 || r >= ROW || c < 0 || c >= COL)
{
return;
}
else if (collection[r][c] == 0)
{
cout << "\n Source are not active \n";
}
else if (collection[x][y] == 0)
{
cout << "\n Destination are not active \n";
}
//Create resultant grid
int output[ROW][COL];
int visitor[ROW][COL];
int i = 0;
int j = 0;
this->length = -1;
//Set initial values
for (i = 0; i < ROW; ++i)
{
for (j = 0; j < COL; ++j)
{
output[i][j] = 0;
visitor[i][j] = 0;
}
}
this->findPath(collection, visitor, output, r, c, x, y, 0);
if (this->length != -1)
{
//When result are exist
cout << "\n Source point (" << r << "," << c << ") Destination point (" << x << "," << y << ") ";
// Display output solution
cout << "\n Longest Path \n";
this->printPath(output);
}
else
{
//When no solution possible
cout << "\n No Result \n";
}
}
};
int main()
{
Maze task = Maze();
int collection[ROW][COL] =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1},
{ 1, 0, 1, 1, 1, 0, 1, 0, 1},
{ 1, 1, 1, 1, 1, 1, 1, 1, 1} ,
{ 0, 1, 1, 0, 0, 1, 1, 1, 1}
};
// Print input problem
cout << "\n Input Maze \n";
task.printPath(collection);
task.longestPath(collection, 0, 0, 3, 6);
task.longestPath(collection, 1, 3, 1, 4);
return 0;
}
Output
Input Maze
1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1 1
Source point (0,0) Destination point (3,6)
Longest Path
1 0 13 14 15 16 17 18 19
2 0 12 11 10 0 0 0 20
3 4 7 8 9 26 25 24 21
0 5 6 0 0 27 28 23 22
Source point (1,3) Destination point (1,4)
Longest Path
9 10 11 12 13 14 15 16 17
8 0 0 1 28 0 0 0 18
7 6 3 2 27 26 23 22 19
0 5 4 0 0 25 24 21 20
// Include namespace system
using System;
/*
C# Program for
Find longest path in maze
*/
public class Maze
{
public int length;
public Maze()
{
this.length = -1;
}
// Print grid elements
public void printPath(int[,] grid, int row, int col)
{
// Loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
Console.Write(" " + grid[i,j] + "\t");
}
Console.Write("\n");
}
Console.Write("\n");
}
// Copy visitor element to output collection
public void copyResult(int[,] visitor, int[,] output, int row, int col)
{
// Loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
// Assign element
output[i,j] = visitor[i,j];
}
}
}
// Find all paths which is exist in given source to destination position
// r and c is Source point
// x and y is destination point
public void findPath(int[,] collection, int[,] visitor, int[,] output, int r, int c, int x, int y, int counter, int row, int col)
{
if (r < 0 || r >= row || c < 0 || c >= col)
{
//When not valid position
return ;
}
else if (r == x && c == y)
{
//When we get destination position
if (visitor[r,c] == 0 && this.length < counter)
{
this.length = counter;
copyResult(visitor, output, row, col);
//When destination are active element
output[r,c] = counter + 1;
}
}
if (visitor[r,c] != 0)
{
//When the element has been already been visited
return ;
}
if (collection[r,c] == 1)
{
//Active visiting node
visitor[r,c] = counter + 1;
//Test four possible direction
findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col);
findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col);
findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col);
findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col);
// Deactivate visited node status
visitor[r,c] = 0;
}
}
//Handles the request to find maze solution
// r and c is Source point
// x and y is destination point
public void longestPath(int[,] collection, int r, int c, int x, int y, int row, int col)
{
// x and y destination point
if (x < 0 || x >= row || y < 0 || y >= col)
{
return;
}
// r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
else if (collection[r,c] == 0)
{
Console.Write("\n Source are not active \n");
}
else if (collection[x,y] == 0)
{
Console.Write("\n Destination are not active \n");
}
//Create resultant grid
int[,] output = new int[row,col];
int[,] visitor = new int[row,col];
int i = 0;
int j = 0;
this.length = -1;
//Set initial values
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
output[i,j] = 0;
visitor[i,j] = 0;
}
}
findPath(collection, visitor, output, r, c, x, y, 0, row, col);
if (length != -1)
{
//When result are exist
Console.Write("\n Source point (" + r + "," + c + ") Destination point (" + x + "," + y + ") ");
// Display output solution
Console.Write("\n Longest Path \n");
printPath(output, row, col);
}
else
{
//When no solution possible
Console.Write("\n No Result \n");
}
}
public static void Main(String[] args)
{
Maze task = new Maze();
int[,] collection =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1},
{ 1, 0, 1, 1, 1, 0, 1, 0, 1},
{ 1, 1, 1, 1, 1, 1, 1, 1, 1},
{ 0, 1, 1, 0, 0, 1, 1, 1, 1}
};
// Get size
int row = collection.GetLength(0);
int col = collection.GetLength(1);
// Print input problem
Console.Write("\n Input Maze \n");
task.printPath(collection, row, col);
task.longestPath(collection, 0, 0, 3, 6, row, col);
task.longestPath(collection, 1, 3, 1, 4, row, col);
}
}
Output
Input Maze
1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1 1
Source point (0,0) Destination point (3,6)
Longest Path
1 0 13 14 15 16 17 18 19
2 0 12 11 10 0 0 0 20
3 4 7 8 9 26 25 24 21
0 5 6 0 0 27 28 23 22
Source point (1,3) Destination point (1,4)
Longest Path
9 10 11 12 13 14 15 16 17
8 0 0 1 28 0 0 0 18
7 6 3 2 27 26 23 22 19
0 5 4 0 0 25 24 21 20
<?php
/*
Php Program for
Find longest path in maze
*/
class Maze
{
public $length;
function __construct()
{
$this->length = -1;
}
// Print grid elements
public function printPath( & $grid, $row, $col)
{
// Loop controlling variables
$i = 0;
$j = 0;
for ($i = 0; $i < $row; ++$i)
{
for ($j = 0; $j < $col; ++$j)
{
echo " ". $grid[$i][$j] ."\t";
}
echo "\n";
}
echo "\n";
}
// Copy visitor element to output collection
public function copyResult( & $visitor, & $output, $row, $col)
{
// Loop controlling variables
$i = 0;
$j = 0;
for ($i = 0; $i < $row; ++$i)
{
for ($j = 0; $j < $col; ++$j)
{
// Assign element
$output[$i][$j] = $visitor[$i][$j];
}
}
}
// Find all paths which is exist in given source to destination position
// r and c is Source point
// x and y is destination point
public function findPath( & $collection, & $visitor, & $output, $r, $c, $x, $y, $counter, $row, $col)
{
if ($r < 0 || $r >= $row || $c < 0 || $c >= $col)
{
//When not valid position
return ;
}
else if ($r == $x && $c == $y)
{
//When we get destination position
if ($visitor[$r][$c] == 0 && $this->length < $counter)
{
$this->length = $counter;
$this->copyResult($visitor, $output, $row, $col);
//When destination are active element
$output[$r][$c] = $counter + 1;
}
}
if ($visitor[$r][$c] != 0)
{
//When the element has been already been visited
return ;
}
if ($collection[$r][$c] == 1)
{
//Active visiting node
$visitor[$r][$c] = $counter + 1;
//Test four possible direction
$this->findPath($collection, $visitor, $output, $r + 1, $c, $x, $y, $counter + 1, $row, $col);
$this->findPath($collection, $visitor, $output, $r, $c + 1, $x, $y, $counter + 1, $row, $col);
$this->findPath($collection, $visitor, $output, $r - 1, $c, $x, $y, $counter + 1, $row, $col);
$this->findPath($collection, $visitor, $output, $r, $c - 1, $x, $y, $counter + 1, $row, $col);
// Deactivate visited node status
$visitor[$r][$c] = 0;
}
}
//Handles the request to find maze solution
// r and c is Source point
// x and y is destination point
public function longestPath( & $collection, $r, $c, $x, $y, $row, $col)
{
// x and y destination point
if ($x < 0 || $x >= $row || $y < 0 || $y >= $col)
{
return;
}
// r and c Source point
if ($r < 0 || $r >= $row || $c < 0 || $c >= $col)
{
return;
}
else if ($collection[$r][$c] == 0)
{
echo "\n Source are not active \n";
}
else if ($collection[$x][$y] == 0)
{
echo "\n Destination are not active \n";
}
//Create resultant grid
$output = array_fill(0, $row, array_fill(0, $col, 0));
$visitor = array_fill(0, $row, array_fill(0, $col, 0));
$this->length = -1;
$this->findPath($collection, $visitor, $output, $r, $c, $x, $y, 0, $row, $col);
if ($this->length != -1)
{
//When result are exist
echo "\n Source point (". $r .",". $c .") Destination point (". $x .",". $y .") ";
// Display output solution
echo "\n Longest Path \n";
$this->printPath($output, $row, $col);
}
else
{
//When no solution possible
echo "\n No Result \n";
}
}
}
function main()
{
$task = new Maze();
$collection = array(
array(1, 1, 1, 1, 1, 1, 1, 1, 1),
array(1, 0, 1, 1, 1, 0, 1, 0, 1),
array(1, 1, 1, 1, 1, 1, 1, 1, 1),
array(0, 1, 1, 0, 0, 1, 1, 1, 1)
);
// Get size
$row = count($collection);
$col = count($collection[0]);
// Print input problem
echo "\n Input Maze \n";
$task->printPath($collection, $row, $col);
$task->longestPath($collection, 0, 0, 3, 6, $row, $col);
$task->longestPath($collection, 1, 3, 1, 4, $row, $col);
}
main();
Output
Input Maze
1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1 1
Source point (0,0) Destination point (3,6)
Longest Path
1 0 13 14 15 16 17 18 19
2 0 12 11 10 0 0 0 20
3 4 7 8 9 26 25 24 21
0 5 6 0 0 27 28 23 22
Source point (1,3) Destination point (1,4)
Longest Path
9 10 11 12 13 14 15 16 17
8 0 0 1 28 0 0 0 18
7 6 3 2 27 26 23 22 19
0 5 4 0 0 25 24 21 20
/*
Node Js Program for
Find longest path in maze
*/
class Maze
{
constructor()
{
this.length = -1;
}
// Print grid elements
printPath(grid, row, col)
{
// Loop controlling variables
var i = 0;
var j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
process.stdout.write(" " + grid[i][j] + "\t");
}
process.stdout.write("\n");
}
process.stdout.write("\n");
}
// Copy visitor element to output collection
copyResult(visitor, output, row, col)
{
// Loop controlling variables
var i = 0;
var j = 0;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
// Assign element
output[i][j] = visitor[i][j];
}
}
}
// Find all paths which is exist in given source to destination position
// r and c is Source point
// x and y is destination point
findPath(collection, visitor, output, r, c, x, y, counter, row, col)
{
if (r < 0 || r >= row || c < 0 || c >= col)
{
//When not valid position
return ;
}
else if (r == x && c == y)
{
//When we get destination position
if (visitor[r][c] == 0 && this.length < counter)
{
this.length = counter;
this.copyResult(visitor, output, row, col);
//When destination are active element
output[r][c] = counter + 1;
}
}
if (visitor[r][c] != 0)
{
//When the element has been already been visited
return ;
}
if (collection[r][c] == 1)
{
//Active visiting node
visitor[r][c] = counter + 1;
//Test four possible direction
this.findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col);
this.findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col);
this.findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col);
this.findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col);
// Deactivate visited node status
visitor[r][c] = 0;
}
}
//Handles the request to find maze solution
// r and c is Source point
// x and y is destination point
longestPath(collection, r, c, x, y, row, col)
{
// x and y destination point
if (x < 0 || x >= row || y < 0 || y >= col)
{
return;
}
// r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
else if (collection[r][c] == 0)
{
process.stdout.write("\n Source are not active \n");
}
else if (collection[x][y] == 0)
{
process.stdout.write("\n Destination are not active \n");
}
//Create resultant grid
var output = Array(row).fill(0).map(() => new Array(col).fill(0));
var visitor = Array(row).fill(0).map(() => new Array(col).fill(0));
this.length = -1;
this.findPath(collection, visitor, output, r, c, x, y, 0, row, col);
if (this.length != -1)
{
//When result are exist
process.stdout.write("\n Source point (" + r + "," + c + ") Destination point (" + x + "," + y + ") ");
// Display output solution
process.stdout.write("\n Longest Path \n");
this.printPath(output, row, col);
}
else
{
//When no solution possible
process.stdout.write("\n No Result \n");
}
}
}
function main()
{
var task = new Maze();
var collection = [
[1, 1, 1, 1, 1, 1, 1, 1, 1] ,
[1, 0, 1, 1, 1, 0, 1, 0, 1] ,
[1, 1, 1, 1, 1, 1, 1, 1, 1] ,
[0, 1, 1, 0, 0, 1, 1, 1, 1]
];
// Get size
var row = collection.length;
var col = collection[0].length;
// Print input problem
process.stdout.write("\n Input Maze \n");
task.printPath(collection, row, col);
task.longestPath(collection, 0, 0, 3, 6, row, col);
task.longestPath(collection, 1, 3, 1, 4, row, col);
}
main();
Output
Input Maze
1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1 1
Source point (0,0) Destination point (3,6)
Longest Path
1 0 13 14 15 16 17 18 19
2 0 12 11 10 0 0 0 20
3 4 7 8 9 26 25 24 21
0 5 6 0 0 27 28 23 22
Source point (1,3) Destination point (1,4)
Longest Path
9 10 11 12 13 14 15 16 17
8 0 0 1 28 0 0 0 18
7 6 3 2 27 26 23 22 19
0 5 4 0 0 25 24 21 20
# Python 3 Program for
# Find longest path in maze
class Maze :
def __init__(self) :
self.length = -1
# Print grid elements
def printPath(self, grid, row, col) :
# Loop controlling variables
i = 0
j = 0
while (i < row) :
j = 0
while (j < col) :
print("", grid[i][j] ,end = "\t")
j += 1
print(end = "\n")
i += 1
print(end = "\n")
# Copy visitor element to output collection
def copyResult(self, visitor, output, row, col) :
# Loop controlling variables
i = 0
j = 0
while (i < row) :
j = 0
while (j < col) :
# Assign element
output[i][j] = visitor[i][j]
j += 1
i += 1
# Find all paths which is exist in given source to destination position
# r and c is Source point
# x and y is destination point
def findPath(self, collection, visitor, output, r, c, x, y, counter, row, col) :
if (r < 0 or r >= row or c < 0 or c >= col) :
# When not valid position
return
elif(r == x and c == y) :
# When we get destination position
if (visitor[r][c] == 0 and self.length < counter) :
self.length = counter
self.copyResult(visitor, output, row, col)
# When destination are active element
output[r][c] = counter + 1
if (visitor[r][c] != 0) :
# When the element has been already been visited
return
if (collection[r][c] == 1) :
# Active visiting node
visitor[r][c] = counter + 1
# Test four possible direction
self.findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col)
self.findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col)
self.findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col)
self.findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col)
# Deactivate visited node status
visitor[r][c] = 0
# Handles the request to find maze solution
# r and c is Source point
# x and y is destination point
def longestPath(self, collection, r, c, x, y, row, col) :
# x and y destination point
if (x < 0 or x >= row or y < 0 or y >= col) :
return
# r and c Source point
if (r < 0 or r >= row or c < 0 or c >= col) :
return
elif(collection[r][c] == 0) :
print("\n Source are not active ")
elif(collection[x][y] == 0) :
print("\n Destination are not active ")
# Create resultant grid
output = [[0] * (col) for _ in range(row) ]
visitor = [[0] * (col) for _ in range(row) ]
self.length = -1
self.findPath(collection, visitor, output, r, c, x, y, 0, row, col)
if (self.length != -1) :
# When result are exist
print("\n Source point (", r ,",", c ,") Destination point (", x ,",", y ,") ", end = "")
# Display output solution
print("\n Longest Path ")
self.printPath(output, row, col)
else :
# When no solution possible
print("\n No Result ")
def main() :
task = Maze()
collection = [
[1, 1, 1, 1, 1, 1, 1, 1, 1] ,
[1, 0, 1, 1, 1, 0, 1, 0, 1] ,
[1, 1, 1, 1, 1, 1, 1, 1, 1] ,
[0, 1, 1, 0, 0, 1, 1, 1, 1]
]
# Get size
row = len(collection)
col = len(collection[0])
# Print input problem
print("\n Input Maze ")
task.printPath(collection, row, col)
task.longestPath(collection, 0, 0, 3, 6, row, col)
task.longestPath(collection, 1, 3, 1, 4, row, col)
if __name__ == "__main__": main()
Output
Input Maze
1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1 1
Source point ( 0 , 0 ) Destination point ( 3 , 6 )
Longest Path
1 0 13 14 15 16 17 18 19
2 0 12 11 10 0 0 0 20
3 4 7 8 9 26 25 24 21
0 5 6 0 0 27 28 23 22
Source point ( 1 , 3 ) Destination point ( 1 , 4 )
Longest Path
9 10 11 12 13 14 15 16 17
8 0 0 1 28 0 0 0 18
7 6 3 2 27 26 23 22 19
0 5 4 0 0 25 24 21 20
# Ruby Program for
# Find longest path in maze
class Maze
# Define the accessor and reader of class Maze
attr_reader :length
attr_accessor :length
def initialize()
self.length = -1
end
# Print grid elements
def printPath(grid, row, col)
# Loop controlling variables
i = 0
j = 0
while (i < row)
j = 0
while (j < col)
print(" ", grid[i][j] ,"\t")
j += 1
end
print("\n")
i += 1
end
print("\n")
end
# Copy visitor element to output collection
def copyResult(visitor, output, row, col)
# Loop controlling variables
i = 0
j = 0
while (i < row)
j = 0
while (j < col)
# Assign element
output[i][j] = visitor[i][j]
j += 1
end
i += 1
end
end
# Find all paths which is exist in given source to destination position
# r and c is Source point
# x and y is destination point
def findPath(collection, visitor, output, r, c, x, y, counter, row, col)
if (r < 0 || r >= row || c < 0 || c >= col)
# When not valid position
return
elsif(r == x && c == y)
# When we get destination position
if (visitor[r][c] == 0 && self.length < counter)
self.length = counter
self.copyResult(visitor, output, row, col)
# When destination are active element
output[r][c] = counter + 1
end
end
if (visitor[r][c] != 0)
# When the element has been already been visited
return
end
if (collection[r][c] == 1)
# Active visiting node
visitor[r][c] = counter + 1
# Test four possible direction
self.findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col)
self.findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col)
self.findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col)
self.findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col)
# Deactivate visited node status
visitor[r][c] = 0
end
end
# Handles the request to find maze solution
# r and c is Source point
# x and y is destination point
def longestPath(collection, r, c, x, y, row, col)
# x and y destination point
if (x < 0 || x >= row || y < 0 || y >= col)
return
end
# r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
return
elsif(collection[r][c] == 0)
print("\n Source are not active \n")
elsif(collection[x][y] == 0)
print("\n Destination are not active \n")
end
# Create resultant grid
output = Array.new(row) {Array.new(col) {0}}
visitor = Array.new(row) {Array.new(col) {0}}
self.length = -1
self.findPath(collection, visitor, output, r, c, x, y, 0, row, col)
if (length != -1)
# When result are exist
print("\n Source point (", r ,",", c ,") Destination point (", x ,",", y ,") ")
# Display output solution
print("\n Longest Path \n")
self.printPath(output, row, col)
else
# When no solution possible
print("\n No Result \n")
end
end
end
def main()
task = Maze.new()
collection = [
[1, 1, 1, 1, 1, 1, 1, 1, 1] ,
[1, 0, 1, 1, 1, 0, 1, 0, 1] ,
[1, 1, 1, 1, 1, 1, 1, 1, 1] ,
[0, 1, 1, 0, 0, 1, 1, 1, 1]
]
# Get size
row = collection.length
col = collection[0].length
# Print input problem
print("\n Input Maze \n")
task.printPath(collection, row, col)
task.longestPath(collection, 0, 0, 3, 6, row, col)
task.longestPath(collection, 1, 3, 1, 4, row, col)
end
main()
Output
Input Maze
1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1 1
Source point (0,0) Destination point (3,6)
Longest Path
1 0 13 14 15 16 17 18 19
2 0 12 11 10 0 0 0 20
3 4 7 8 9 26 25 24 21
0 5 6 0 0 27 28 23 22
Source point (1,3) Destination point (1,4)
Longest Path
9 10 11 12 13 14 15 16 17
8 0 0 1 28 0 0 0 18
7 6 3 2 27 26 23 22 19
0 5 4 0 0 25 24 21 20
/*
Scala Program for
Find longest path in maze
*/
class Maze(var length: Int)
{
def this()
{
this(-1);
}
// Print grid elements
def printPath(grid: Array[Array[Int]], row: Int, col: Int): Unit = {
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
while (i < row)
{
j = 0;
while (j < col)
{
print(" " + grid(i)(j) + "\t");
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Copy visitor element to output collection
def copyResult(visitor: Array[Array[Int]], output: Array[Array[Int]], row: Int, col: Int): Unit = {
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
while (i < row)
{
j = 0;
while (j < col)
{
// Assign element
output(i)(j) = visitor(i)(j);
j += 1;
}
i += 1;
}
}
// Find all paths which is exist in given source to destination position
// r and c is Source point
// x and y is destination point
def findPath(collection: Array[Array[Int]], visitor: Array[Array[Int]], output: Array[Array[Int]], r: Int, c: Int, x: Int, y: Int, counter: Int, row: Int, col: Int): Unit = {
if (r < 0 || r >= row || c < 0 || c >= col)
{
//When not valid position
return ;
}
else if (r == x && c == y)
{
//When we get destination position
if (visitor(r)(c) == 0 && this.length < counter)
{
this.length = counter;
this.copyResult(visitor, output, row, col);
//When destination are active element
output(r)(c) = counter + 1;
}
}
if (visitor(r)(c) != 0)
{
//When the element has been already been visited
return ;
}
if (collection(r)(c) == 1)
{
//Active visiting node
visitor(r)(c) = counter + 1;
//Test four possible direction
this.findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col);
this.findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col);
this.findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col);
this.findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col);
// Deactivate visited node status
visitor(r)(c) = 0;
}
}
//Handles the request to find maze solution
// r and c is Source point
// x and y is destination point
def longestPath(collection: Array[Array[Int]], r: Int, c: Int, x: Int, y: Int, row: Int, col: Int): Unit = {
// x and y destination point
if (x < 0 || x >= row || y < 0 || y >= col)
{
return;
}
// r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
else if (collection(r)(c) == 0)
{
print("\n Source are not active \n");
}
else if (collection(x)(y) == 0)
{
print("\n Destination are not active \n");
}
//Create resultant grid
var output: Array[Array[Int]] = Array.fill[Int](row, col)(0);
var visitor: Array[Array[Int]] = Array.fill[Int](row, col)(0);
this.length = -1;
this.findPath(collection, visitor, output, r, c, x, y, 0, row, col);
if (length != -1)
{
//When result are exist
print("\n Source point (" + r + "," + c + ") Destination point (" + x + "," + y + ") ");
// Display output solution
print("\n Longest Path \n");
this.printPath(output, row, col);
}
else
{
//When no solution possible
print("\n No Result \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Maze = new Maze();
var collection: Array[Array[Int]] = Array(
Array(1, 1, 1, 1, 1, 1, 1, 1, 1),
Array(1, 0, 1, 1, 1, 0, 1, 0, 1),
Array(1, 1, 1, 1, 1, 1, 1, 1, 1),
Array(0, 1, 1, 0, 0, 1, 1, 1, 1)
);
// Get size
var row: Int = collection.length;
var col: Int = collection(0).length;
// Print input problem
print("\n Input Maze \n");
task.printPath(collection, row, col);
task.longestPath(collection, 0, 0, 3, 6, row, col);
task.longestPath(collection, 1, 3, 1, 4, row, col);
}
}
Output
Input Maze
1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1 1
Source point (0,0) Destination point (3,6)
Longest Path
1 0 13 14 15 16 17 18 19
2 0 12 11 10 0 0 0 20
3 4 7 8 9 26 25 24 21
0 5 6 0 0 27 28 23 22
Source point (1,3) Destination point (1,4)
Longest Path
9 10 11 12 13 14 15 16 17
8 0 0 1 28 0 0 0 18
7 6 3 2 27 26 23 22 19
0 5 4 0 0 25 24 21 20
/*
Swift 4 Program for
Find longest path in maze
*/
class Maze
{
var length: Int;
init()
{
self.length = -1;
}
// Print grid elements
func printPath(_ grid: [[Int]], _ row: Int, _ col: Int)
{
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
while (i < row)
{
j = 0;
while (j < col)
{
print("", grid[i][j], terminator: "\t");
j += 1;
}
print(terminator: "\n");
i += 1;
}
print(terminator: "\n");
}
// Copy visitor element to output collection
func copyResult(_ visitor: [[Int]], _ output: inout[[Int]], _ row: Int, _ col: Int)
{
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
while (i < row)
{
j = 0;
while (j < col)
{
// Assign element
output[i][j] = visitor[i][j];
j += 1;
}
i += 1;
}
}
// Find all paths which is exist in given source to destination position
// r and c is Source point
// x and y is destination point
func findPath(_ collection: [[Int]], _ visitor: inout[[Int]], _ output: inout[[Int]], _ r: Int, _ c: Int, _ x: Int, _ y: Int, _ counter: Int, _ row: Int, _ col: Int)
{
if (r < 0 || r >= row || c < 0 || c >= col)
{
//When not valid position
return;
}
else if (r == x && c == y)
{
//When we get destination position
if (visitor[r][c] == 0 && self.length < counter)
{
self.length = counter;
self.copyResult(visitor, &output, row, col);
//When destination are active element
output[r][c] = counter + 1;
}
}
if (visitor[r][c] != 0)
{
//When the element has been already been visited
return;
}
if (collection[r][c] == 1)
{
//Active visiting node
visitor[r][c] = counter + 1;
//Test four possible direction
self.findPath(collection, &visitor, &output, r + 1, c, x, y, counter + 1, row, col);
self.findPath(collection, &visitor, &output, r, c + 1, x, y, counter + 1, row, col);
self.findPath(collection, &visitor, &output, r - 1, c, x, y, counter + 1, row, col);
self.findPath(collection, &visitor, &output, r, c - 1, x, y, counter + 1, row, col);
// Deactivate visited node status
visitor[r][c] = 0;
}
}
//Handles the request to find maze solution
// r and c is Source point
// x and y is destination point
func longestPath(_ collection: [[Int]], _ r: Int, _ c: Int, _ x: Int, _ y: Int, _ row: Int, _ col: Int)
{
// x and y destination point
if (x < 0 || x >= row || y < 0 || y >= col)
{
return;
}
// r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
else if (collection[r][c] == 0)
{
print("\n Source are not active ");
}
else if (collection[x][y] == 0)
{
print("\n Destination are not active ");
}
//Create resultant grid
var output: [[Int]] = Array(repeating: Array(repeating: 0, count: col), count: row);
var visitor: [[Int]] = Array(repeating: Array(repeating: 0, count: col), count: row);
self.length = -1;
self.findPath(collection, &visitor, &output, r, c, x, y, 0, row, col);
if (self.length != -1)
{
//When result are exist
print("\n Source point (", r ,",", c ,") Destination point (", x ,",", y ,") ", terminator: "");
// Display output solution
print("\n Longest Path ");
self.printPath(output, row, col);
}
else
{
//When no solution possible
print("\n No Result ");
}
}
}
func main()
{
let task: Maze = Maze();
let collection: [[Int]] = [
[1, 1, 1, 1, 1, 1, 1, 1, 1] ,
[1, 0, 1, 1, 1, 0, 1, 0, 1] ,
[1, 1, 1, 1, 1, 1, 1, 1, 1] ,
[0, 1, 1, 0, 0, 1, 1, 1, 1]
];
// Get size
let row: Int = collection.count;
let col: Int = collection[0].count;
// Print input problem
print("\n Input Maze ");
task.printPath(collection, row, col);
task.longestPath(collection, 0, 0, 3, 6, row, col);
task.longestPath(collection, 1, 3, 1, 4, row, col);
}
main();
Output
Input Maze
1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1 1
Source point ( 0 , 0 ) Destination point ( 3 , 6 )
Longest Path
1 0 13 14 15 16 17 18 19
2 0 12 11 10 0 0 0 20
3 4 7 8 9 26 25 24 21
0 5 6 0 0 27 28 23 22
Source point ( 1 , 3 ) Destination point ( 1 , 4 )
Longest Path
9 10 11 12 13 14 15 16 17
8 0 0 1 28 0 0 0 18
7 6 3 2 27 26 23 22 19
0 5 4 0 0 25 24 21 20
/*
Kotlin Program for
Find longest path in maze
*/
class Maze
{
var length: Int;
constructor()
{
this.length = -1;
}
// Print grid elements
fun printPath(grid: Array<Array<Int>> , row: Int, col: Int): Unit
{
// Loop controlling variables
var i: Int = 0;
var j: Int ;
while (i < row)
{
j = 0;
while (j < col)
{
print(" " + grid[i][j] + "\t");
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Copy visitor element to output collection
fun copyResult(visitor: Array<Array<Int>> , output: Array <Array<Int>> , row: Int, col: Int): Unit
{
// Loop controlling variables
var i: Int = 0;
var j: Int ;
while (i < row)
{
j = 0;
while (j < col)
{
// Assign element
output[i][j] = visitor[i][j];
j += 1;
}
i += 1;
}
}
// Find all paths which is exist in given source to destination position
// r and c is Source point
// x and y is destination point
fun findPath(collection: Array <Array <Int>> , visitor: Array <Array<Int>> , output: Array <Array<Int>> , r: Int, c: Int, x: Int, y: Int, counter: Int, row: Int, col: Int)
{
if (r < 0 || r >= row || c < 0 || c >= col)
{
//When not valid position
return ;
}
else if (r == x && c == y)
{
//When we get destination position
if (visitor[r][c] == 0 && this.length < counter)
{
this.length = counter;
this.copyResult(visitor, output, row, col);
//When destination are active element
output[r][c] = counter + 1;
}
}
if (visitor[r][c] != 0)
{
//When the element has been already been visited
return ;
}
if (collection[r][c] == 1)
{
//Active visiting node
visitor[r][c] = counter + 1;
//Test four possible direction
this.findPath(collection, visitor, output, r + 1, c, x, y, counter + 1, row, col);
this.findPath(collection, visitor, output, r, c + 1, x, y, counter + 1, row, col);
this.findPath(collection, visitor, output, r - 1, c, x, y, counter + 1, row, col);
this.findPath(collection, visitor, output, r, c - 1, x, y, counter + 1, row, col);
// Deactivate visited node status
visitor[r][c] = 0;
}
}
//Handles the request to find maze solution
// r and c is Source point
// x and y is destination point
fun longestPath(collection: Array <Array <Int>> , r: Int, c: Int, x: Int, y: Int, row: Int, col: Int): Unit
{
// x and y destination point
if (x < 0 || x >= row || y < 0 || y >= col)
{
return;
}
// r and c Source point
if (r < 0 || r >= row || c < 0 || c >= col)
{
return;
}
else if (collection[r][c] == 0)
{
print("\n Source are not active \n");
}
else if (collection[x][y] == 0)
{
print("\n Destination are not active \n");
}
//Create resultant grid
var output: Array < Array < Int >> = Array(row)
{
Array(col)
{
0
}
};
var visitor: Array < Array < Int >> = Array(row)
{
Array(col)
{
0
}
};
this.length = -1;
this.findPath(collection, visitor, output, r, c, x, y, 0, row, col);
if (length != -1)
{
//When result are exist
print("\n Source point (" + r + "," + c + ") Destination point (" + x + "," + y + ") ");
// Display output solution
print("\n Longest Path \n");
this.printPath(output, row, col);
}
else
{
//When no solution possible
print("\n No Result \n");
}
}
}
fun main(args: Array < String > ): Unit
{
var task: Maze = Maze();
var collection: Array <Array<Int>> = arrayOf(
arrayOf(1, 1, 1, 1, 1, 1, 1, 1, 1),
arrayOf(1, 0, 1, 1, 1, 0, 1, 0, 1),
arrayOf(1, 1, 1, 1, 1, 1, 1, 1, 1),
arrayOf(0, 1, 1, 0, 0, 1, 1, 1, 1)
);
// Get size
var row: Int = collection.count();
var col: Int = collection[0].count();
// Print input problem
print("\n Input Maze \n");
task.printPath(collection, row, col);
task.longestPath(collection, 0, 0, 3, 6, row, col);
task.longestPath(collection, 1, 3, 1, 4, row, col);
}
Output
Input Maze
1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1 1
Source point (0,0) Destination point (3,6)
Longest Path
1 0 13 14 15 16 17 18 19
2 0 12 11 10 0 0 0 20
3 4 7 8 9 26 25 24 21
0 5 6 0 0 27 28 23 22
Source point (1,3) Destination point (1,4)
Longest Path
9 10 11 12 13 14 15 16 17
8 0 0 1 28 0 0 0 18
7 6 3 2 27 26 23 22 19
0 5 4 0 0 25 24 21 20
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