Skip to main content

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)
    {
        Maze task = new Maze();
        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");
        task.printMaze(maze, n);
        // Test cases
        task.findPath(maze,n, 0, 5);
        task.findPath(maze,n, 1, 3);
        task.findPath(maze,n, 2, 3);
    }
}

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 header file
#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()
{
	Maze task = Maze();
	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";
	task.printMaze(maze);
	// Test cases
	task.findPath(maze, 0, 5);
	task.findPath(maze, 1, 3);
	task.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
// 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)
	{
		Maze task = new Maze();
		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");
		task.printMaze(maze, n);
		// Test cases
		task.findPath(maze, n, 0, 5);
		task.findPath(maze, n, 1, 3);
		task.findPath(maze, n, 2, 3);
	}
}

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()
{
	$task = new Maze();
	$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";
	$task->printMaze($maze, $n);
	// Test cases
	$task->findPath($maze, $n, 0, 5);
	$task->findPath($maze, $n, 1, 3);
	$task->findPath($maze, $n, 2, 3);
}
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 task = new Maze();
	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");
	task.printMaze(maze, n);
	// Test cases
	task.findPath(maze, n, 0, 5);
	task.findPath(maze, n, 1, 3);
	task.findPath(maze, n, 2, 3);
}
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() :
	task = Maze()
	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 ")
	task.printMaze(maze, n)
	#  Test cases
	task.findPath(maze, n, 0, 5)
	task.findPath(maze, n, 1, 3)
	task.findPath(maze, n, 2, 3)

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() 
	task = Maze.new()
	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")
	task.printMaze(maze, n)
	#  Test cases
	task.findPath(maze, n, 0, 5)
	task.findPath(maze, n, 1, 3)
	task.findPath(maze, n, 2, 3)
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");
		task.printMaze(maze, n);
		// Test cases
		task.findPath(maze, n, 0, 5);
		task.findPath(maze, n, 1, 3);
		task.findPath(maze, n, 2, 3);
	}
}

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 task: Maze = Maze();
	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 ");
	task.printMaze(maze, n);
	// Test cases
	task.findPath(maze, n, 0, 5);
	task.findPath(maze, n, 1, 3);
	task.findPath(maze, n, 2, 3);
}
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 task: Maze = Maze();
	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");
	task.printMaze(maze, n);
	// Test cases
	task.findPath(maze, n, 0, 5);
	task.findPath(maze, n, 1, 3);
	task.findPath(maze, n, 2, 3);
}

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.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment