Posted on by Kalkicode
Code Backtracking

# Locate the center path of given maze by using footprint

The task at hand is to develop a program that can navigate through a given maze and locate the center path using a footprint approach. The maze is represented as a 2D grid, and the goal is to find a path from the source position to the center of the maze.

## Problem Statement

We are given a maze represented by a grid, where each cell contains a number indicating the maximum number of steps that can be taken from that cell. The objective is to find a path from a given source position to the center of the maze. The center of the maze is determined by the dimensions of the grid, where the row and column indices are both equal to N / 2, where N is the size of the grid. The path must adhere to the following rules:

1. The path can only move horizontally or vertically, not diagonally.
2. Each step taken in the path must not exceed the value in the current cell.
3. Once a cell has been visited, it cannot be revisited.

## Example

Let's consider the following maze:

6	4	3	3	4	2	3
1	1	4	3	5	5	3
4	7	5	6	3	2	3
5	3	4	4	3	5	2
6	3	7	3	5	4	4
2	1	3	3	5	6	3
3	6	4	3	2	4	5

If we start at the source position (0, 5), we can find the center path as follows:

Source (0,5) Location
13	-	-	-	12	1	9
-	5	6	-	-	-	7
-	-	-	-	-	2	-
-	-	-	16	11	-	10
-	4	-	-	-	3	8
-	-	-	-	-	-	-
14	-	-	15	-	-	-

Here, the numbers represent the steps taken to reach each cell along the path. Empty cells are denoted by hyphens ("-").

## Algorithm

To solve this problem, we can use a recursive approach. Here is the pseudocode algorithm:

function findRoute(maze, output, r, c, result):
if r < 0 or r >= N or c < 0 or c >= N:
return 0
else if r == N / 2 and c == N / 2:
output[r][c] = result
return 1
if output[r][c] != 0:
return 0
if maze[r][c] < N:
output[r][c] = result
if findRoute(maze, output, r + maze[r][c], c, result + 1) or
findRoute(maze, output, r, c + maze[r][c], result + 1) or
findRoute(maze, output, r - maze[r][c], c, result + 1) or
findRoute(maze, output, r, c - maze[r][c], result + 1):
return 1
output[r][c] = 0
return 0

function findPath(maze, x, y):
create an output grid
for each cell in the output grid:
set the value to 0
if findRoute(maze, output, x, y, 1):
print the resulting path
else:
print "No result"

maze = the given maze
print the input maze
for each test case:
find the path from the given source position to the center of the maze

## Code Solution

// C program
// Navigate a path from source to center of maze
#include <stdio.h>

#define N 7
//Print grid elements
void printMaze(int grid[N][N])
{
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
printf("%d\t", grid[i][j]);
}
printf("\n");
}
printf("\n");
}
//Print result elements
void printResult(int output[N][N])
{
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
if (output[i][j] != 0)
{
printf("%d\t", output[i][j]);
}
else
{
printf("-\t");
}
}
printf("\n");
}
printf("\n");
}
// Find path from source to center
// If solutions are not exist then it returns 0 (False).
int findRoute(int maze[N][N], int output[N][N], int r, int c, int result)
{
if (r < 0 || r >= N || c < 0 || c >= N)
{
// When location is not reachable location
// Outside range
return 0;
}
else if (r == N / 2 && c == N / 2)
{
// When we get destination position
output[r][c] = result;
return 1;
}
if (output[r][c] != 0)
{
// When the element has been already been visited
return 0;
}
if (maze[r][c] < N)
{
// Active visiting node
output[r][c] = result;
// Test four possible direction
if (findRoute(maze, output, r + maze[r][c], c, result + 1)
||
findRoute(maze, output, r, c + maze[r][c], result + 1)
||
findRoute(maze, output, r - maze[r][c], c, result + 1)
||
findRoute(maze, output, r, c - maze[r][c], result + 1))
{
return 1;
}
// Deactivate visited node status
output[r][c] = 0;
}
return 0;
}
//Handles the request to find maze solution
void findPath(int maze[N][N], int x, int y)
{
//Create resultant grid
int output[N][N];
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
output[i][j] = 0;
}
}
printf("\n Source (%d,%d) Location \n",x,y);
if (findRoute(maze, output, x, y, 1))
{

printResult(output);
}
else
{
//When no solution possible
printf(" No Result \n");
}
}
int main()
{
int maze[N][N] =
{
{6, 4, 3, 3, 4, 2, 3},
{1, 1, 4, 3, 5, 5, 3},
{4, 7, 5, 6, 3, 2, 3},
{5, 3, 4, 4, 3, 5, 2},
{6, 3, 7, 3, 5, 4, 4},
{2, 1, 3, 3, 5, 6, 3},
{3, 6, 4, 3, 2, 4, 5}

};

// Print input problem
printf("\n  Input Maze \n");
printMaze(maze);

// Test cases
findPath(maze, 0, 5);
findPath(maze, 1, 3);
findPath(maze, 2, 3);

return 0;
}

#### Output

Input Maze
6	4	3	3	4	2	3
1	1	4	3	5	5	3
4	7	5	6	3	2	3
5	3	4	4	3	5	2
6	3	7	3	5	4	4
2	1	3	3	5	6	3
3	6	4	3	2	4	5

Source (0,5) Location
13	-	-	-	12	1	9
-	5	6	-	-	-	7
-	-	-	-	-	2	-
-	-	-	16	11	-	10
-	4	-	-	-	3	8
-	-	-	-	-	-	-
14	-	-	15	-	-	-

Source (1,3) Location
-	10	-	-	-	-	4
13	12	-	1	-	-	-
14	-	-	-	-	-	-
-	-	-	17	6	-	5
-	11	-	2	-	-	3
-	-	-	-	-	-	-
15	9	-	16	7	-	8

Source (2,3) Location
No Result
/*
Java Program for
Navigate a path from source to center of maze
*/
class Maze
{
// Print grid elements
public void printMaze(int[][] grid, int n)
{
int i = 0;
int j = 0;
// Set initial values
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
System.out.print(grid[i][j] + "\t");
}
System.out.print("\n");
}
System.out.print("\n");
}
// Print result elements
public void printResult(int[][] output, int n)
{
int i = 0;
int j = 0;
// Set initial values
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
if (output[i][j] != 0)
{
System.out.print(output[i][j] + "\t");
}
else
{
System.out.print("-\t");
}
}
System.out.print("\n");
}
System.out.print("\n");
}
// Find path from source to center
// If solutions are not exist then it returns 0 (False).
public boolean findRoute(int[][] maze, int[][] output, int r, int c, int n, int result)
{
if (r < 0 || r >= n || c < 0 || c >= n)
{
// When location is not reachable location
// Outside range
return false;
}
else if (r == n / 2 && c == n / 2)
{
// When we get destination position
output[r][c] = result;
return true;
}
if (output[r][c] != 0)
{
// When the element has been already been visited
return false;
}
if (maze[r][c] < n)
{
// Active visiting node
output[r][c] = result;
// Test four possible direction
if (findRoute(maze, output, r + maze[r][c], c, n, result + 1)
|| findRoute(maze, output, r, c + maze[r][c], n, result + 1)
|| findRoute(maze, output, r - maze[r][c], c, n, result + 1)
|| findRoute(maze, output, r, c - maze[r][c], n, result + 1)
)
{
return true;
}
// Deactivate visited node status
output[r][c] = 0;
}
return false;
}
// Handles the request to find maze solution
public void findPath(int[][] maze,int n, int x, int y)
{

// Create resultant grid
int[][] output = new int[n][n];
int i = 0;
int j = 0;
// Set initial values
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
output[i][j] = 0;
}
}
System.out.print("\n Source ("+x+","+y+") Location \n");
if (findRoute(maze, output, x, y,n, 1))
{
// When result are exist
// Display output solution
printResult(output, n);
}
else
{
//When no solution possible
System.out.print("\n No Result \n");
}
}
public static void main(String[] args)
{
int[][] maze =
{
{6, 4, 3, 3, 4, 2, 3},
{1, 1, 4, 3, 5, 5, 3},
{4, 7, 5, 6, 3, 2, 3},
{5, 3, 4, 4, 3, 5, 2},
{6, 3, 7, 3, 5, 4, 4},
{2, 1, 3, 3, 5, 6, 3},
{3, 6, 4, 3, 2, 4, 5}
};
// n*n maze
int n = maze.length;
// Print input problem
System.out.print("\n Input Maze \n");
// Test cases
}
}

#### Output

Input Maze
6	4	3	3	4	2	3
1	1	4	3	5	5	3
4	7	5	6	3	2	3
5	3	4	4	3	5	2
6	3	7	3	5	4	4
2	1	3	3	5	6	3
3	6	4	3	2	4	5

Source (0,5) Location
13	-	-	-	12	1	9
-	5	6	-	-	-	7
-	-	-	-	-	2	-
-	-	-	16	11	-	10
-	4	-	-	-	3	8
-	-	-	-	-	-	-
14	-	-	15	-	-	-

Source (1,3) Location
-	10	-	-	-	-	4
13	12	-	1	-	-	-
14	-	-	-	-	-	-
-	-	-	17	6	-	5
-	11	-	2	-	-	3
-	-	-	-	-	-	-
15	9	-	16	7	-	8

Source (2,3) Location

No Result
#include <iostream>
#define N 7
using namespace std;
/*
C++ Program for
Navigate a path from source to center of maze
*/
class Maze
{
public:
// Print grid elements
void printMaze(int grid[N][N])
{
int i = 0;
int j = 0;
// Set initial values
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
cout << grid[i][j] << "\t";
}
cout << "\n";
}
cout << "\n";
}
// Print result elements
void printResult(int output[N][N])
{
int i = 0;
int j = 0;
// Set initial values
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
if (output[i][j] != 0)
{
cout << output[i][j] << "\t";
}
else
{
cout << "-\t";
}
}
cout << "\n";
}
cout << "\n";
}
// Find path from source to center
// If solutions are not exist then it returns 0 (False).
bool findRoute(int maze[N][N], int output[N][N], int r, int c, int result)
{
if (r < 0 || r >= N || c < 0 || c >=N)
{
// When location is not reachable location
// Outside range
return false;
}
else if (r == N / 2 && c == N / 2)
{
// When we get destination position
output[r][c] = result;
return true;
}
if (output[r][c] != 0)
{
// When the element has been already been visited
return false;
}
if (maze[r][c] < N)
{
// Active visiting node
output[r][c] = result;
// Test four possible direction
if (this->findRoute(maze, output, r + maze[r][c], c, result + 1)
|| this->findRoute(maze, output, r, c + maze[r][c], result + 1)
|| this->findRoute(maze, output, r - maze[r][c], c, result + 1)
|| this->findRoute(maze, output, r, c - maze[r][c], result + 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = 0;
}
return false;
}
// Handles the request to find maze solution
void findPath(int maze[N][N], int x, int y)
{
// Create resultant grid
int output[N][N];
int i = 0;
int j = 0;
// Set initial values
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
output[i][j] = 0;
}
}
cout << "\n Source (" << x << "," << y << ") Location \n";
if (this->findRoute(maze, output, x, y, 1))
{
// When result are exist
// Display output solution
this->printResult(output);
}
else
{
//When no solution possible
cout << "\n No Result \n";
}
}
};
int main()
{
int maze[N][N] = {
{
6 , 4 , 3 , 3 , 4 , 2 , 3
} , {
1 , 1 , 4 , 3 , 5 , 5 , 3
} , {
4 , 7 , 5 , 6 , 3 , 2 , 3
} , {
5 , 3 , 4 , 4 , 3 , 5 , 2
} , {
6 , 3 , 7 , 3 , 5 , 4 , 4
} , {
2 , 1 , 3 , 3 , 5 , 6 , 3
} , {
3 , 6 , 4 , 3 , 2 , 4 , 5
}
};

// Print input problem
cout << "\n Input Maze \n";
// Test cases
return 0;
}

#### Output

Input Maze
6	4	3	3	4	2	3
1	1	4	3	5	5	3
4	7	5	6	3	2	3
5	3	4	4	3	5	2
6	3	7	3	5	4	4
2	1	3	3	5	6	3
3	6	4	3	2	4	5

Source (0,5) Location
13	-	-	-	12	1	9
-	5	6	-	-	-	7
-	-	-	-	-	2	-
-	-	-	16	11	-	10
-	4	-	-	-	3	8
-	-	-	-	-	-	-
14	-	-	15	-	-	-

Source (1,3) Location
-	10	-	-	-	-	4
13	12	-	1	-	-	-
14	-	-	-	-	-	-
-	-	-	17	6	-	5
-	11	-	2	-	-	3
-	-	-	-	-	-	-
15	9	-	16	7	-	8

Source (2,3) Location

No Result
// Include namespace system
using System;
/*
C# Program for
Navigate a path from source to center of maze
*/
public class Maze
{
// Print grid elements
public void printMaze(int[,] grid, int n)
{
int i = 0;
int j = 0;
// Set initial values
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
Console.Write(grid[i,j] + "\t");
}
Console.Write("\n");
}
Console.Write("\n");
}
// Print result elements
public void printResult(int[,] output, int n)
{
int i = 0;
int j = 0;
// Set initial values
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
if (output[i,j] != 0)
{
Console.Write(output[i,j] + "\t");
}
else
{
Console.Write("-\t");
}
}
Console.Write("\n");
}
Console.Write("\n");
}
// Find path from source to center
// If solutions are not exist then it returns 0 (False).
public Boolean findRoute(int[,] maze, int[,] output, int r, int c, int n, int result)
{
if (r < 0 || r >= n || c < 0 || c >= n)
{
// When location is not reachable location
// Outside range
return false;
}
else if (r == n / 2 && c == n / 2)
{
// When we get destination position
output[r,c] = result;
return true;
}
if (output[r,c] != 0)
{
// When the element has been already been visited
return false;
}
if (maze[r,c] < n)
{
// Active visiting node
output[r,c] = result;
// Test four possible direction
if (findRoute(maze, output, r + maze[r,c], c, n, result + 1)
|| findRoute(maze, output, r, c + maze[r,c], n, result + 1)
|| findRoute(maze, output, r - maze[r,c], c, n, result + 1)
|| findRoute(maze, output, r, c - maze[r,c], n, result + 1))
{
return true;
}
// Deactivate visited node status
output[r,c] = 0;
}
return false;
}
// Handles the request to find maze solution
public void findPath(int[,] maze, int n, int x, int y)
{
// Create resultant grid
int[,] output = new int[n,n];
int i = 0;
int j = 0;
// Set initial values
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
output[i,j] = 0;
}
}
Console.Write("\n Source (" + x + "," + y + ") Location \n");
if (findRoute(maze, output, x, y, n, 1))
{
// When result are exist
// Display output solution
printResult(output, n);
}
else
{
//When no solution possible
Console.Write("\n No Result \n");
}
}
public static void Main(String[] args)
{
int[,] maze =
{
{6, 4, 3, 3, 4, 2, 3},
{1, 1, 4, 3, 5, 5, 3},
{4, 7, 5, 6, 3, 2, 3},
{5, 3, 4, 4, 3, 5, 2},
{6, 3, 7, 3, 5, 4, 4},
{2, 1, 3, 3, 5, 6, 3},
{3, 6, 4, 3, 2, 4, 5}
};
// n*n maze
int n = maze.GetLength(0);
// Print input problem
Console.Write("\n Input Maze \n");
// Test cases
}
}

#### Output

Input Maze
6	4	3	3	4	2	3
1	1	4	3	5	5	3
4	7	5	6	3	2	3
5	3	4	4	3	5	2
6	3	7	3	5	4	4
2	1	3	3	5	6	3
3	6	4	3	2	4	5

Source (0,5) Location
13	-	-	-	12	1	9
-	5	6	-	-	-	7
-	-	-	-	-	2	-
-	-	-	16	11	-	10
-	4	-	-	-	3	8
-	-	-	-	-	-	-
14	-	-	15	-	-	-

Source (1,3) Location
-	10	-	-	-	-	4
13	12	-	1	-	-	-
14	-	-	-	-	-	-
-	-	-	17	6	-	5
-	11	-	2	-	-	3
-	-	-	-	-	-	-
15	9	-	16	7	-	8

Source (2,3) Location

No Result
<?php
/*
Php Program for
Navigate a path from source to center of maze
*/
class Maze
{
// Print grid elements
public function printMaze(\$grid, \$n)
{
\$i = 0;
\$j = 0;
// Set initial values
for (\$i = 0; \$i < \$n; ++\$i)
{
for (\$j = 0; \$j < \$n; ++\$j)
{
echo \$grid[\$i][\$j] ."\t";
}
echo "\n";
}
echo "\n";
}
// Print result elements
public function printResult( & \$output, \$n)
{
\$i = 0;
\$j = 0;
// Set initial values
for (\$i = 0; \$i < \$n; ++\$i)
{
for (\$j = 0; \$j < \$n; ++\$j)
{
if (\$output[\$i][\$j] != 0)
{
echo \$output[\$i][\$j] ."\t";
}
else
{
echo "-\t";
}
}
echo "\n";
}
echo "\n";
}
// Find path from source to center
// If solutions are not exist then it returns 0 (False).
public function findRoute( & \$maze, & \$output, \$r, \$c, \$n, \$result)
{
if (\$r < 0 || \$r >= \$n || \$c < 0 || \$c >= \$n)
{
// When location is not reachable location
// Outside range
return false;
}
else if (\$r == intval(\$n / 2) && \$c == intval(\$n / 2))
{
// When we get destination position
\$output[\$r][\$c] = \$result;
return true;
}
if (\$output[\$r][\$c] != 0)
{
// When the element has been already been visited
return false;
}
if (\$maze[\$r][\$c] < \$n)
{
// Active visiting node
\$output[\$r][\$c] = \$result;
// Test four possible direction
if (\$this->findRoute(\$maze, \$output, \$r + \$maze[\$r][\$c], \$c, \$n, \$result + 1)
|| \$this->findRoute(\$maze, \$output, \$r, \$c + \$maze[\$r][\$c], \$n, \$result + 1)
|| \$this->findRoute(\$maze, \$output, \$r - \$maze[\$r][\$c], \$c, \$n, \$result + 1)
|| \$this->findRoute(\$maze, \$output, \$r, \$c - \$maze[\$r][\$c], \$n, \$result + 1))
{
return true;
}
// Deactivate visited node status
\$output[\$r][\$c] = 0;
}
return false;
}
// Handles the request to find maze solution
public	function findPath( & \$maze, \$n, \$x, \$y)
{
// Create resultant grid
\$output = array_fill(0, \$n, array_fill(0, \$n, 0));
echo "\n Source (". \$x .",". \$y .") Location \n";
if (\$this->findRoute(\$maze, \$output, \$x, \$y, \$n, 1))
{
// When result are exist
// Display output solution
\$this->printResult(\$output, \$n);
}
else
{
//When no solution possible
echo "\n No Result \n";
}
}
}

function main()
{
\$maze = array(
array(6, 4, 3, 3, 4, 2, 3),
array(1, 1, 4, 3, 5, 5, 3),
array(4, 7, 5, 6, 3, 2, 3),
array(5, 3, 4, 4, 3, 5, 2),
array(6, 3, 7, 3, 5, 4, 4),
array(2, 1, 3, 3, 5, 6, 3),
array(3, 6, 4, 3, 2, 4, 5)
);
// n*n maze
\$n = count(\$maze);
// Print input problem
echo "\n Input Maze \n";
// Test cases
}
main();

#### Output

Input Maze
6	4	3	3	4	2	3
1	1	4	3	5	5	3
4	7	5	6	3	2	3
5	3	4	4	3	5	2
6	3	7	3	5	4	4
2	1	3	3	5	6	3
3	6	4	3	2	4	5

Source (0,5) Location
13	-	-	-	12	1	9
-	5	6	-	-	-	7
-	-	-	-	-	2	-
-	-	-	16	11	-	10
-	4	-	-	-	3	8
-	-	-	-	-	-	-
14	-	-	15	-	-	-

Source (1,3) Location
-	10	-	-	-	-	4
13	12	-	1	-	-	-
14	-	-	-	-	-	-
-	-	-	17	6	-	5
-	11	-	2	-	-	3
-	-	-	-	-	-	-
15	9	-	16	7	-	8

Source (2,3) Location

No Result
/*
Node Js Program for
Navigate a path from source to center of maze
*/
class Maze
{
// Print grid elements
printMaze(grid, n)
{
var i = 0;
var j = 0;
// Set initial values
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
process.stdout.write(grid[i][j] + "\t");
}
process.stdout.write("\n");
}
process.stdout.write("\n");
}
// Print result elements
printResult(output, n)
{
var i = 0;
var j = 0;
// Set initial values
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
if (output[i][j] != 0)
{
process.stdout.write(output[i][j] + "\t");
}
else
{
process.stdout.write("-\t");
}
}
process.stdout.write("\n");
}
process.stdout.write("\n");
}
// Find path from source to center
// If solutions are not exist then it returns 0 (False).
findRoute(maze, output, r, c, n, result)
{
if (r < 0 || r >= n || c < 0 || c >= n)
{
// When location is not reachable location
// Outside range
return false;
}
else if (r == parseInt(n / 2) && c == parseInt(n / 2))
{
// When we get destination position
output[r][c] = result;
return true;
}
if (output[r][c] != 0)
{
// When the element has been already been visited
return false;
}
if (maze[r][c] < n)
{
// Active visiting node
output[r][c] = result;
// Test four possible direction
if (this.findRoute(maze, output, r + maze[r][c], c, n, result + 1)
|| this.findRoute(maze, output, r, c + maze[r][c], n, result + 1)
|| this.findRoute(maze, output, r - maze[r][c], c, n, result + 1)
|| this.findRoute(maze, output, r, c - maze[r][c], n, result + 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = 0;
}
return false;
}
// Handles the request to find maze solution
findPath(maze, n, x, y)
{
// Create resultant grid
var output = Array(n).fill(0).map(() => new Array(n).fill(0));
process.stdout.write("\n Source (" + x + "," + y + ") Location \n");
if (this.findRoute(maze, output, x, y, n, 1))
{
// When result are exist
// Display output solution
this.printResult(output, n);
}
else
{
//When no solution possible
process.stdout.write("\n No Result \n");
}
}
}

function main()
{
var maze = [
[6, 4, 3, 3, 4, 2, 3] ,
[1, 1, 4, 3, 5, 5, 3] ,
[4, 7, 5, 6, 3, 2, 3] ,
[5, 3, 4, 4, 3, 5, 2] ,
[6, 3, 7, 3, 5, 4, 4] ,
[2, 1, 3, 3, 5, 6, 3] ,
[3, 6, 4, 3, 2, 4, 5]
];
// n*n maze
var n = maze.length;
// Print input problem
process.stdout.write("\n Input Maze \n");
// Test cases
}
main();

#### Output

Input Maze
6	4	3	3	4	2	3
1	1	4	3	5	5	3
4	7	5	6	3	2	3
5	3	4	4	3	5	2
6	3	7	3	5	4	4
2	1	3	3	5	6	3
3	6	4	3	2	4	5

Source (0,5) Location
13	-	-	-	12	1	9
-	5	6	-	-	-	7
-	-	-	-	-	2	-
-	-	-	16	11	-	10
-	4	-	-	-	3	8
-	-	-	-	-	-	-
14	-	-	15	-	-	-

Source (1,3) Location
-	10	-	-	-	-	4
13	12	-	1	-	-	-
14	-	-	-	-	-	-
-	-	-	17	6	-	5
-	11	-	2	-	-	3
-	-	-	-	-	-	-
15	9	-	16	7	-	8

Source (2,3) Location

No Result
#   Python 3 Program for
#   Navigate a path from source to center of maze

class Maze :
#  Print grid elements
def printMaze(self, grid, n) :
i = 0
j = 0
#  Set initial values
while (i < n) :
j = 0
while (j < n) :
print(grid[i][j] ,"\t", end = "")
j += 1

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

print(end = "\n")

#  Print result elements
def printResult(self, output, n) :
i = 0
j = 0
#  Set initial values
while (i < n) :
j = 0
while (j < n) :
if (output[i][j] != 0) :
print(output[i][j] ,"\t", end = "")
else :
print("-\t", end = "")

j += 1

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

print(end = "\n")

#  Find path from source to center
#  If solutions are not exist then it returns 0 (False).
def findRoute(self, maze, output, r, c, n, result) :
if (r < 0 or r >= n or c < 0 or c >= n) :
#  When location is not reachable location
#  Outside range
return False

elif(r == int(n / 2) and c == int(n / 2)) :
#  When we get destination position
output[r][c] = result
return True

if (output[r][c] != 0) :
#  When the element has been already been visited
return False

if (maze[r][c] < n) :
#  Active visiting node
output[r][c] = result
#  Test four possible direction
if (self.findRoute(maze, output, r + maze[r][c], c, n, result + 1)
or self.findRoute(maze, output, r, c + maze[r][c], n, result + 1)
or self.findRoute(maze, output, r - maze[r][c], c, n, result + 1)
or self.findRoute(maze, output, r, c - maze[r][c], n, result + 1)) :
return True

#  Deactivate visited node status
output[r][c] = 0

return False

#  Handles the request to find maze solution
def findPath(self, maze, n, x, y) :
#  Create resultant grid
output = [[0] * (n) for _ in range(n) ]
print("\n Source (", x ,",", y ,") Location ")
if (self.findRoute(maze, output, x, y, n, 1)) :
#  When result are exist
#  Display output solution
self.printResult(output, n)
else :
# When no solution possible
print("\n No Result ")

def main() :
maze = [
[6, 4, 3, 3, 4, 2, 3] , [1, 1, 4, 3, 5, 5, 3] , [4, 7, 5, 6, 3, 2, 3] , [5, 3, 4, 4, 3, 5, 2] , [6, 3, 7, 3, 5, 4, 4] , [2, 1, 3, 3, 5, 6, 3] , [3, 6, 4, 3, 2, 4, 5]
]
#  n*n maze
n = len(maze)
#  Print input problem
print("\n Input Maze ")
#  Test cases

if __name__ == "__main__": main()

#### Output

Input Maze
6 	4 	3 	3 	4 	2 	3
1 	1 	4 	3 	5 	5 	3
4 	7 	5 	6 	3 	2 	3
5 	3 	4 	4 	3 	5 	2
6 	3 	7 	3 	5 	4 	4
2 	1 	3 	3 	5 	6 	3
3 	6 	4 	3 	2 	4 	5

Source ( 0 , 5 ) Location
13 	-	-	-	12 	1 	9
-	5 	6 	-	-	-	7
-	-	-	-	-	2 	-
-	-	-	16 	11 	-	10
-	4 	-	-	-	3 	8
-	-	-	-	-	-	-
14 	-	-	15 	-	-	-

Source ( 1 , 3 ) Location
-	10 	-	-	-	-	4
13 	12 	-	1 	-	-	-
14 	-	-	-	-	-	-
-	-	-	17 	6 	-	5
-	11 	-	2 	-	-	3
-	-	-	-	-	-	-
15 	9 	-	16 	7 	-	8

Source ( 2 , 3 ) Location

No Result
#   Ruby Program for
#   Navigate a path from source to center of maze

class Maze
#  Print grid elements
def printMaze(grid, n)
i = 0
j = 0
#  Set initial values
while (i < n)
j = 0
while (j < n)
print(grid[i][j] ,"\t")
j += 1
end

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

print("\n")
end

#  Print result elements
def printResult(output, n)
i = 0
j = 0
#  Set initial values
while (i < n)
j = 0
while (j < n)
if (output[i][j] != 0)
print(output[i][j] ,"\t")
else
print("-\t")
end

j += 1
end

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

print("\n")
end

#  Find path from source to center
#  If solutions are not exist then it returns 0 (False).
def findRoute(maze, output, r, c, n, result)
if (r < 0 || r >= n || c < 0 || c >= n)
#  When location is not reachable location
#  Outside range
return false
elsif(r == n / 2 && c == n / 2)
#  When we get destination position
output[r][c] = result
return true
end

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

if (maze[r][c] < n)
#  Active visiting node
output[r][c] = result
#  Test four possible direction
if (   self.findRoute(maze, output, r + maze[r][c], c, n, result + 1) ||
self.findRoute(maze, output, r, c + maze[r][c], n, result + 1) ||
self.findRoute(maze, output, r - maze[r][c], c, n, result + 1) ||
self.findRoute(maze, output, r, c - maze[r][c], n, result + 1))
return true
end

#  Deactivate visited node status
output[r][c] = 0
end

return false
end

#  Handles the request to find maze solution
def findPath(maze, n, x, y)
#  Create resultant grid
output = Array.new(n) {Array.new(n) {0}}
print("\n Source (", x ,",", y ,") Location \n")
if (self.findRoute(maze, output, x, y, n, 1))
#  When result are exist
#  Display output solution
self.printResult(output, n)
else
# When no solution possible
print("\n No Result \n")
end

end

end

def main()
maze = [
[6, 4, 3, 3, 4, 2, 3] ,
[1, 1, 4, 3, 5, 5, 3] ,
[4, 7, 5, 6, 3, 2, 3] ,
[5, 3, 4, 4, 3, 5, 2] ,
[6, 3, 7, 3, 5, 4, 4] ,
[2, 1, 3, 3, 5, 6, 3] ,
[3, 6, 4, 3, 2, 4, 5]
]
#  n*n maze
n = maze.length
#  Print input problem
print("\n Input Maze \n")
#  Test cases
end

main()

#### Output

Input Maze
6	4	3	3	4	2	3
1	1	4	3	5	5	3
4	7	5	6	3	2	3
5	3	4	4	3	5	2
6	3	7	3	5	4	4
2	1	3	3	5	6	3
3	6	4	3	2	4	5

Source (0,5) Location
13	-	-	-	12	1	9
-	5	6	-	-	-	7
-	-	-	-	-	2	-
-	-	-	16	11	-	10
-	4	-	-	-	3	8
-	-	-	-	-	-	-
14	-	-	15	-	-	-

Source (1,3) Location
-	10	-	-	-	-	4
13	12	-	1	-	-	-
14	-	-	-	-	-	-
-	-	-	17	6	-	5
-	11	-	2	-	-	3
-	-	-	-	-	-	-
15	9	-	16	7	-	8

Source (2,3) Location

No Result
/*
Scala Program for
Navigate a path from source to center of maze
*/
class Maze
{
// Print grid elements
def printMaze(grid: Array[Array[Int]], n: Int): Unit = {
var i: Int = 0;
var j: Int = 0;
// Set initial values
while (i < n)
{
j = 0;
while (j < n)
{
print(""+grid(i)(j) + "\t");
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Print result elements
def printResult(output: Array[Array[Int]], n: Int): Unit = {
var i: Int = 0;
var j: Int = 0;
// Set initial values
while (i < n)
{
j = 0;
while (j < n)
{
if (output(i)(j) != 0)
{
print(""+output(i)(j) + "\t");
}
else
{
print("-\t");
}
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Find path from source to center
// If solutions are not exist then it returns 0 (False).
def findRoute(maze: Array[Array[Int]], output: Array[Array[Int]], r: Int, c: Int, n: Int, result: Int): Boolean = {
if (r < 0 || r >= n || c < 0 || c >= n)
{
// When location is not reachable location
// Outside range
return false;
}
else if (r == (n / 2).toInt && c == (n / 2).toInt)
{
// When we get destination position
output(r)(c) = result;
return true;
}
if (output(r)(c) != 0)
{
// When the element has been already been visited
return false;
}
if (maze(r)(c) < n)
{
// Active visiting node
output(r)(c) = result;
// Test four possible direction
if (this.findRoute(maze, output, r + maze(r)(c), c, n, result + 1)
|| this.findRoute(maze, output, r, c + maze(r)(c), n, result + 1)
|| this.findRoute(maze, output, r - maze(r)(c), c, n, result + 1)
|| this.findRoute(maze, output, r, c - maze(r)(c), n, result + 1))
{
return true;
}
// Deactivate visited node status
output(r)(c) = 0;
}
return false;
}
// Handles the request to find maze solution
def findPath(maze: Array[Array[Int]], n: Int, x: Int, y: Int): Unit = {
// Create resultant grid
var output: Array[Array[Int]] = Array.fill[Int](n, n)(0);
print("\n Source (" + x + "," + y + ") Location \n");
if (this.findRoute(maze, output, x, y, n, 1))
{
// When result are exist
// Display output solution
this.printResult(output, n);
}
else
{
//When no solution possible
print("\n No Result \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Maze = new Maze();
var maze: Array[Array[Int]] = Array(
Array(6, 4, 3, 3, 4, 2, 3),
Array(1, 1, 4, 3, 5, 5, 3),
Array(4, 7, 5, 6, 3, 2, 3),
Array(5, 3, 4, 4, 3, 5, 2),
Array(6, 3, 7, 3, 5, 4, 4),
Array(2, 1, 3, 3, 5, 6, 3),
Array(3, 6, 4, 3, 2, 4, 5)
);
// n*n maze
var n: Int = maze.length;
// Print input problem
print("\n Input Maze \n");
// Test cases
}
}

#### Output

Input Maze
6	4	3	3	4	2	3
1	1	4	3	5	5	3
4	7	5	6	3	2	3
5	3	4	4	3	5	2
6	3	7	3	5	4	4
2	1	3	3	5	6	3
3	6	4	3	2	4	5

Source (0,5) Location
13	-	-	-	12	1	9
-	5	6	-	-	-	7
-	-	-	-	-	2	-
-	-	-	16	11	-	10
-	4	-	-	-	3	8
-	-	-	-	-	-	-
14	-	-	15	-	-	-

Source (1,3) Location
-	10	-	-	-	-	4
13	12	-	1	-	-	-
14	-	-	-	-	-	-
-	-	-	17	6	-	5
-	11	-	2	-	-	3
-	-	-	-	-	-	-
15	9	-	16	7	-	8

Source (2,3) Location

No Result
/*
Swift 4 Program for
Navigate a path from source to center of maze
*/
class Maze
{
// Print grid elements
func printMaze(_ grid: [[Int]], _ n: Int)
{
var i: Int = 0;
var j: Int = 0;
// Set initial values
while (i < n)
{
j = 0;
while (j < n)
{
print(grid[i][j] , terminator:"\t");
j += 1;
}
print(terminator: "\n");
i += 1;
}
print(terminator: "\n");
}
// Print result elements
func printResult(_ output: [[Int]], _ n: Int)
{
var i: Int = 0;
var j: Int = 0;
// Set initial values
while (i < n)
{
j = 0;
while (j < n)
{
if (output[i][j]  != 0)
{
print(output[i][j], terminator: "\t");
}
else
{
print(terminator: "-\t");
}
j += 1;
}
print(terminator: "\n");
i += 1;
}
print(terminator: "\n");
}
// Find path from source to center
// If solutions are not exist then it returns 0 (False).
func findRoute(_ maze: [[Int]], _ output: inout[[Int]], _ r: Int, _ c: Int, _ n: Int, _ result: Int)->Bool
{
if (r < 0 || r >= n || c < 0 || c >= n)
{
// When location is not reachable location
// Outside range
return false;
}
else if (r == n / 2 && c == n / 2)
{
// When we get destination position
output[r][c] = result;
return true;
}
if (output[r][c]  != 0)
{
// When the element has been already been visited
return false;
}
if (maze[r][c] < n)
{
// Active visiting node
output[r][c] = result;
// Test four possible direction
if (self.findRoute(maze, &output, r + maze[r][c], c, n, result + 1)
|| self.findRoute(maze, &output, r, c + maze[r][c], n, result + 1)
|| self.findRoute(maze, &output, r - maze[r][c], c, n, result + 1)
|| self.findRoute(maze, &output, r, c - maze[r][c], n, result + 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = 0;
}
return false;
}
// Handles the request to find maze solution
func findPath(_ maze: [[Int]], _ n: Int, _ x: Int, _ y: Int)
{
// Create resultant grid
var output: [[Int]] = Array(repeating: Array(repeating: 0, count: n), count: n);
print("\n Source (", x ,",", y ,") Location ");
if (self.findRoute(maze, &output, x, y, n, 1))
{
// When result are exist
// Display output solution
self.printResult(output, n);
}
else
{
//When no solution possible
print("\n No Result ");
}
}
}
func main()
{
let maze: [[Int]] = [
[6, 4, 3, 3, 4, 2, 3] ,
[1, 1, 4, 3, 5, 5, 3] ,
[4, 7, 5, 6, 3, 2, 3] ,
[5, 3, 4, 4, 3, 5, 2] ,
[6, 3, 7, 3, 5, 4, 4] ,
[2, 1, 3, 3, 5, 6, 3] ,
[3, 6, 4, 3, 2, 4, 5]
];
// n*n maze
let n: Int = maze.count;
// Print input problem
print("\n Input Maze ");
// Test cases
}
main();

#### Output

Input Maze
6	4	3	3	4	2	3
1	1	4	3	5	5	3
4	7	5	6	3	2	3
5	3	4	4	3	5	2
6	3	7	3	5	4	4
2	1	3	3	5	6	3
3	6	4	3	2	4	5

Source ( 0 , 5 ) Location
13	-	-	-	12	1	9
-	5	6	-	-	-	7
-	-	-	-	-	2	-
-	-	-	16	11	-	10
-	4	-	-	-	3	8
-	-	-	-	-	-	-
14	-	-	15	-	-	-

Source ( 1 , 3 ) Location
-	10	-	-	-	-	4
13	12	-	1	-	-	-
14	-	-	-	-	-	-
-	-	-	17	6	-	5
-	11	-	2	-	-	3
-	-	-	-	-	-	-
15	9	-	16	7	-	8

Source ( 2 , 3 ) Location

No Result
/*
Kotlin Program for
Navigate a path from source to center of maze
*/
class Maze
{
// Print grid elements
fun printMaze(grid: Array <Array<Int>> , n: Int): Unit
{
var i: Int = 0;
var j: Int ;
// Set initial values
while (i < n)
{
j = 0;
while (j < n)
{
print(""+grid[i][j] + "\t");
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Print result elements
fun printResult(output: Array<Array<Int>> , n: Int): Unit
{
var i: Int = 0;
var j: Int ;
// Set initial values
while (i < n)
{
j = 0;
while (j < n)
{
if (output[i][j] != 0)
{
print(""+output[i][j] + "\t");
}
else
{
print("-\t");
}
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Find path from source to center
// If solutions are not exist then it returns 0 (False).
fun findRoute(maze: Array < Array < Int >> , output: Array < Array < Int >> , r: Int, c: Int, n: Int, result: Int): Boolean
{
if (r < 0 || r >= n || c < 0 || c >= n)
{
// When location is not reachable location
// Outside range
return false;
}
else if (r == n / 2 && c == n / 2)
{
// When we get destination position
output[r][c] = result;
return true;
}
if (output[r][c] != 0)
{
// When the element has been already been visited
return false;
}
if (maze[r][c] < n)
{
// Active visiting node
output[r][c] = result;
// Test four possible direction
if (this.findRoute(maze, output, r + maze[r][c], c, n, result + 1)
|| this.findRoute(maze, output, r, c + maze[r][c], n, result + 1)
|| this.findRoute(maze, output, r - maze[r][c], c, n, result + 1)
|| this.findRoute(maze, output, r, c - maze[r][c], n, result + 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = 0;
}
return false;
}
// Handles the request to find maze solution
fun findPath(maze: Array < Array < Int >> , n: Int, x: Int, y: Int): Unit
{
// Create resultant grid
var output: Array < Array < Int >> = Array(n)
{
Array(n)
{
0
}
};
print("\n Source (" + x + "," + y + ") Location \n");
if (this.findRoute(maze, output, x, y, n, 1))
{
// When result are exist
// Display output solution
this.printResult(output, n);
}
else
{
//When no solution possible
print("\n No Result \n");
}
}
}
fun main(args: Array < String > ): Unit
{
var maze: Array<Array<Int>> = arrayOf(
arrayOf(6, 4, 3, 3, 4, 2, 3),
arrayOf(1, 1, 4, 3, 5, 5, 3),
arrayOf(4, 7, 5, 6, 3, 2, 3),
arrayOf(5, 3, 4, 4, 3, 5, 2),
arrayOf(6, 3, 7, 3, 5, 4, 4),
arrayOf(2, 1, 3, 3, 5, 6, 3),
arrayOf(3, 6, 4, 3, 2, 4, 5)
);
// n*n maze
var n: Int = maze.count();
// Print input problem
print("\n Input Maze \n");
// Test cases
}

#### Output

Input Maze
6	4	3	3	4	2	3
1	1	4	3	5	5	3
4	7	5	6	3	2	3
5	3	4	4	3	5	2
6	3	7	3	5	4	4
2	1	3	3	5	6	3
3	6	4	3	2	4	5

Source (0,5) Location
13	-	-	-	12	1	9
-	5	6	-	-	-	7
-	-	-	-	-	2	-
-	-	-	16	11	-	10
-	4	-	-	-	3	8
-	-	-	-	-	-	-
14	-	-	15	-	-	-

Source (1,3) Location
-	10	-	-	-	-	4
13	12	-	1	-	-	-
14	-	-	-	-	-	-
-	-	-	17	6	-	5
-	11	-	2	-	-	3
-	-	-	-	-	-	-
15	9	-	16	7	-	8

Source (2,3) Location

No Result

## Time Complexity

The time complexity of this algorithm is determined by the number of cells in the grid. Since we explore each cell only once, the time complexity is O(N^2), where N is the size of the grid.

## Finally

In this article, we explored the problem of locating the center path of a maze using a footprint approach. We examined the problem statement, provided a suitable example, explained the pseudocode algorithm, and discussed the time complexity of the solution. By following the steps outlined in the algorithm, we can successfully find the center path of a given maze. This approach can be applied to various maze-solving scenarios and can be a useful tool in pathfinding algorithms and game development.

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

Categories
Relative Post