Posted on by Kalkicode
Code Backtracking

Find all possible path with one magical key in maze

Here given code implementation process.

/*
    C Program 
    Find all possible path with one magical key in maze
*/
#include <stdio.h>

#define N 4
#define M 6
// Display calculated path
void printPath(int track[N][M])
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (track[i][j] == 1)
			{
				printf("\t1");
			}
			else
			{
				printf("\t-");
			}
		}
		printf("\n");
	}
	printf("\n\n");
}
// Find all paths using an active (1) key from top to bottom right
void findPath(int maze[N][M], int track[N][M], int i, int j, int active)
{
	if (i < 0 || j < 0 || i == N || j == M || track[i][j] == 1 || (active == 1 && maze[i][j] == 1))
	{
		// stop process
		return;
	}
	if (i == N - 1 && j == M - 1)
	{
		if ((maze[i][j] == 1 && active == 0) || (maze[i][j] == 0 && active == 1))
		{
			// When path contains one active key
			track[i][j] = 1;
			// Display path
			printPath(track);
			track[i][j] = 0;
		}
		return;
	}
	// Visit element activated
	track[i][j] = 1;
	if (maze[i][j] == 0 || active == 0)
	{
		int status = active;
		if (maze[i][j] == 1)
		{
			status = 1;
		}
		// Pick direction
		// Down
		findPath(maze, track, i + 1, j, status);
		// Right
		findPath(maze, track, i, j + 1, status);
		// Left
		findPath(maze, track, i, j - 1, status);
		// Top
		findPath(maze, track, i - 1, j, status);
	}
	// Deactivate visit element
	track[i][j] = 0;
}
// Handles the request to find active key path
void testPath(int maze[N][M])
{
	int track[N][M];
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			track[i][j] = 0;
		}
	}
	// Find path
	findPath(maze, track, 0, 0, 0);
}
int main()
{
    int maze[N][M] =
    {
        {0,0,0,0,0,0},
        {1,1,0,1,1,0},
        {1,0,1,1,1,0},
        {1,0,0,0,0,0}
    };
	testPath(maze);
	return 0;
}

Output

	1	1	-	-	-	-
	-	1	-	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	1	1	-	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	-	1	-	-	-
	-	-	1	1	1	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	1	1	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	-	1	1	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	1	1	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	-
	-	-	-	-	1	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	1	1	1
	-	-	-	-	-	1
	-	-	-	-	1	1
	-	-	-	-	1	1


/*
  Java Program for
  Find all possible path with one magical key in maze
*/
public class MazePath
{
	// Display calculated path
	public void printPath(boolean[][] track, int n, int m)
	{
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (track[i][j] == true)
				{
					System.out.print("\t1");
				}
				else
				{
					System.out.print("\t-");
				}
			}
			System.out.print("\n");
		}
		System.out.print("\n\n");
	}
	// Find all paths using an active (1) key from top to bottom right
	public void findPath(int[][] maze, boolean[][] track, int i, int j, int n, int m, boolean active)
	{
		if (i < 0 || j < 0 || i == n || j == m || track[i][j] == true || (active == true && maze[i][j] == 1))
		{
			// Stop process
			return;
		}
		if (i == n - 1 && j == m - 1)
		{
			if ((maze[i][j] == 1 && active == false) || (maze[i][j] == 0 && active == true))
			{
				// When path contains one active key
				track[i][j] = true;
				// Display path
				printPath(track, n, m);
				track[i][j] = false;
			}
			return;
		}
		// Visit element activated
		track[i][j] = true;
		if (maze[i][j] == 0 || active == false)
		{
			boolean status = active;
			if (maze[i][j] == 1)
			{
				status = true;
			}
			// Pick direction
			// Down
			findPath(maze, track, i + 1, j, n, m, status);
			// Right
			findPath(maze, track, i, j + 1, n, m, status);
			// Left
			findPath(maze, track, i, j - 1, n, m, status);
			// Top
			findPath(maze, track, i - 1, j, n, m, status);
		}
		// Deactivate visit element
		track[i][j] = false;
	}
	// Handles the request to find active key path
	public void testPath(int[][] maze)
	{
		// Rows
		int n = maze.length;
		// Column
		int m = maze[0].length;
		boolean[][] track = new boolean[n][m];
		// Set default value
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				track[i][j] = false;
			}
		}
		// Find path
		findPath(maze, track, 0, 0, n, m, false);
	}
	public static void main(String[] args)
	{
		MazePath task = new MazePath();
        int [][]maze =
        {
            {0,0,0,0,0,0},
            {1,1,0,1,1,0},
            {1,0,1,1,1,0},
            {1,0,0,0,0,0}
        };
		task.testPath(maze);
	}
}

Output

	1	1	-	-	-	-
	-	1	-	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	1	1	-	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	-	1	-	-	-
	-	-	1	1	1	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	1	1	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	-	1	1	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	1	1	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	-
	-	-	-	-	1	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	1	1	1
	-	-	-	-	-	1
	-	-	-	-	1	1
	-	-	-	-	1	1


// Include header file
#include <iostream>
#define N 4
#define M 6
using namespace std;

/*
  C++ Program for
  Find all possible path with one magical key in maze
*/

class MazePath
{
    public:
    // Display calculated path
    void printPath(bool track[N][M])
    {
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < M; ++j)
            {
                if (track[i][j] == true)
                {
                    cout << "\t1";
                }
                else
                {
                    cout << "\t-";
                }
            }
            cout << "\n";
        }
        cout << "\n\n";
    }
    // Find all paths using an active (1) key from top to bottom right
    void findPath(int maze[N][M], bool track[N][M], int i, int j, bool active)
    {
        // Stop process
        if (i < 0 || j < 0 || i == N || j == M || track[i][j] == true || (active == true && maze[i][j] == 1))
        {
            return;
        }
        if (i == N - 1 && j == M - 1)
        {
            if ((maze[i][j] == 1 && active == false) || (maze[i][j] == 0 && active == true))
            {
                // When path contains one active key
                track[i][j] = true;
                // Display path
                this->printPath(track);
                track[i][j] = false;
            }
            return;
        }
        // Visit element activated
        track[i][j] = true;
        if (maze[i][j] == 0 || active == false)
        {
            bool status = active;
            if (maze[i][j] == 1)
            {
                status = true;
            }
            // Pick direction
            // Down
            this->findPath(maze, track, i + 1, j, status);
            // Right
            this->findPath(maze, track, i, j + 1, status);
            // Left
            this->findPath(maze, track, i, j - 1, status);
            // Top
            this->findPath(maze, track, i - 1, j, status);
        }
        // Deactivate visit element
        track[i][j] = false;
    }
    // Handles the request to find active key path
    void testPath(int maze[N][M])
    {

        bool track[N][M];
        // Set default value
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < M; ++j)
            {
                track[i][j] = false;
            }
        }
        // Find path
        this->findPath(maze, track, 0, 0, false);
    }
};
int main()
{
    MazePath task = MazePath();
    int maze[N][M] = 
    {
        {0, 0, 0, 0, 0, 0},
        {1, 1, 0, 1, 1, 0},
        {1, 0, 1, 1, 1, 0},
        {1, 0, 0, 0, 0, 0}
    };
    task.testPath(maze);
    return 0;
}

Output

	1	1	-	-	-	-
	-	1	-	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	1	1	-	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	-	1	-	-	-
	-	-	1	1	1	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	1	1	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	-	1	1	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	1	1	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	-
	-	-	-	-	1	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	1	1	1
	-	-	-	-	-	1
	-	-	-	-	1	1
	-	-	-	-	1	1


// Include namespace system
using System;
/*
  C# Program for
  Find all possible path with one magical key in maze
*/
public class MazePath
{
	// Display calculated path
	public void printPath(Boolean[,] track, int n, int m)
	{
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (track[i,j] == true)
				{
					Console.Write("\t1");
				}
				else
				{
					Console.Write("\t-");
				}
			}
			Console.Write("\n");
		}
		Console.Write("\n\n");
	}
	// Find all paths using an active (1) key from top to bottom right
	public void findPath(int[,] maze, Boolean[,] track, int i, int j, int n, int m, Boolean active)
	{
		// Stop process
		if (i < 0 || j < 0 || i == n || j == m || track[i,j] == true || (active == true && maze[i,j] == 1))
		{
			return;
		}
		if (i == n - 1 && j == m - 1)
		{
			if ((maze[i,j] == 1 && active == false) || (maze[i,j] == 0 && active == true))
			{
				// When path contains one active key
				track[i,j] = true;
				// Display path
				printPath(track, n, m);
				track[i,j] = false;
			}
			return;
		}
		// Visit element activated
		track[i,j] = true;
		if (maze[i,j] == 0 || active == false)
		{
			Boolean status = active;
			if (maze[i,j] == 1)
			{
				status = true;
			}
			// Pick direction
			// Down
			findPath(maze, track, i + 1, j, n, m, status);
			// Right
			findPath(maze, track, i, j + 1, n, m, status);
			// Left
			findPath(maze, track, i, j - 1, n, m, status);
			// Top
			findPath(maze, track, i - 1, j, n, m, status);
		}
		// Deactivate visit element
		track[i,j] = false;
	}
	// Handles the request to find active key path
	public void testPath(int[,] maze)
	{
		// Rows
		int n = maze.GetLength(0);
		// Column
		int m = maze.GetLength(1);
		Boolean[,] track = new Boolean[n,m];
		// Set default value
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				track[i,j] = false;
			}
		}
		// Find path
		findPath(maze, track, 0, 0, n, m, false);
	}
	public static void Main(String[] args)
	{
		MazePath task = new MazePath();
		int[,] maze = {
			{
				0 , 0 , 0 , 0 , 0 , 0
			} , {
				1 , 1 , 0 , 1 , 1 , 0
			} , {
				1 , 0 , 1 , 1 , 1 , 0
			} , {
				1 , 0 , 0 , 0 , 0 , 0
			}
		};
		task.testPath(maze);
	}
}

Output

	1	1	-	-	-	-
	-	1	-	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	1	1	-	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	-	1	-	-	-
	-	-	1	1	1	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	1	1	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	-	1	1	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	1	1	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	-
	-	-	-	-	1	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	1	1	1
	-	-	-	-	-	1
	-	-	-	-	1	1
	-	-	-	-	1	1


<?php
/*
  Php Program for
  Find all possible path with one magical key in maze
*/
class MazePath
{
	// Display calculated path
	public	function printPath($track, $n, $m)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			for ($j = 0; $j < $m; ++$j)
			{
				if ($track[$i][$j] == true)
				{
					echo "\t1";
				}
				else
				{
					echo "\t-";
				}
			}
			echo "\n";
		}
		echo "\n\n";
	}
	// Find all paths using an active (1) key from top to bottom right
	public	function findPath( $maze, & $track, $i, $j, $n, $m, $active)
	{
		// Stop process
		if ($i < 0 || $j < 0 || $i == $n || $j == $m 
            || $track[$i][$j] == true || 
            ($active == true && $maze[$i][$j] == 1))
		{
			return;
		}
		if ($i == $n - 1 && $j == $m - 1)
		{
			if (($maze[$i][$j] == 1 && $active == false) 
                || ($maze[$i][$j] == 0 && $active == true))
			{
				// When path contains one active key
				$track[$i][$j] = true;
				// Display path
				$this->printPath($track, $n, $m);
				$track[$i][$j] = false;
			}
			return;
		}
		// Visit element activated
		$track[$i][$j] = true;
		if ($maze[$i][$j] == 0 || $active == false)
		{
			$status = $active;
			if ($maze[$i][$j] == 1)
			{
				$status = true;
			}
			// Pick direction
			// Down
			$this->findPath($maze, $track, $i + 1, $j, $n, $m, $status);
			// Right
			$this->findPath($maze, $track, $i, $j + 1, $n, $m, $status);
			// Left
			$this->findPath($maze, $track, $i, $j - 1, $n, $m, $status);
			// Top
			$this->findPath($maze, $track, $i - 1, $j, $n, $m, $status);
		}
		// Deactivate visit element
		$track[$i][$j] = false;
	}
	// Handles the request to find active key path
	public	function testPath( & $maze)
	{
		// Rows
		$n = count($maze);
		// Column
		$m =  count($maze[0]);
		$track = array_fill(0, $n, array_fill(0, $m, false));
		// Find path
		$this->findPath($maze, $track, 0, 0, $n, $m, false);
	}
}

function main()
{
	$task = new MazePath();
	$maze = array(
      array(0, 0, 0, 0, 0, 0), 
      array(1, 1, 0, 1, 1, 0), 
      array(1, 0, 1, 1, 1, 0), 
      array(1, 0, 0, 0, 0, 0)
    );
	$task->testPath($maze);
}
main();

Output

	1	1	-	-	-	-
	-	1	-	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	1	1	-	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	-	1	-	-	-
	-	-	1	1	1	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	1	1	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	-	1	1	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	1	1	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	-
	-	-	-	-	1	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	1	1	1
	-	-	-	-	-	1
	-	-	-	-	1	1
	-	-	-	-	1	1


/*
  Node Js Program for
  Find all possible path with one magical key in maze
*/
class MazePath
{
	// Display calculated path
	printPath(track, n, m)
	{
		for (var i = 0; i < n; ++i)
		{
			for (var j = 0; j < m; ++j)
			{
				if (track[i][j] == true)
				{
					process.stdout.write("\t1");
				}
				else
				{
					process.stdout.write("\t-");
				}
			}
			process.stdout.write("\n");
		}
		process.stdout.write("\n\n");
	}
	// Find all paths using an active (1) key from top to bottom right
	findPath(maze, track, i, j, n, m, active)
	{
		// Stop process
		if (i < 0 || j < 0 || i == n || j == m || track[i][j] == true || (active == true && maze[i][j] == 1))
		{
			return;
		}
		if (i == n - 1 && j == m - 1)
		{
			if ((maze[i][j] == 1 && active == false) || (maze[i][j] == 0 && active == true))
			{
				// When path contains one active key
				track[i][j] = true;
				// Display path
				this.printPath(track, n, m);
				track[i][j] = false;
			}
			return;
		}
		// Visit element activated
		track[i][j] = true;
		if (maze[i][j] == 0 || active == false)
		{
			var status = active;
			if (maze[i][j] == 1)
			{
				status = true;
			}
			// Pick direction
			// Down
			this.findPath(maze, track, i + 1, j, n, m, status);
			// Right
			this.findPath(maze, track, i, j + 1, n, m, status);
			// Left
			this.findPath(maze, track, i, j - 1, n, m, status);
			// Top
			this.findPath(maze, track, i - 1, j, n, m, status);
		}
		// Deactivate visit element
		track[i][j] = false;
	}
	// Handles the request to find active key path
	testPath(maze)
	{
		// Rows
		var n = maze.length;
		// Column
		var m = maze[0].length;
		var track = Array(n).fill(false).map(() => new Array(m).fill(false));
		// Find path
		this.findPath(maze, track, 0, 0, n, m, false);
	}
}

function main()
{
	var task = new MazePath();
	var maze = [
	  [0, 0, 0, 0, 0, 0] , 
      [1, 1, 0, 1, 1, 0] , 
      [1, 0, 1, 1, 1, 0] , 
      [1, 0, 0, 0, 0, 0]
	];
	task.testPath(maze);
}
main();

Output

	1	1	-	-	-	-
	-	1	-	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	1	1	-	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	-	1	-	-	-
	-	-	1	1	1	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	1	1	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	-	1	1	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	1	1	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	-
	-	-	-	-	1	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	1	1	1
	-	-	-	-	-	1
	-	-	-	-	1	1
	-	-	-	-	1	1


#   Python 3 Program for
#   Find all possible path with one magical key in maze

class MazePath :
	#  Display calculated path
	def printPath(self, track, n, m) :
		i = 0
		j = 0
		while (i < n) :
			while (j < m) :
				if (track[i][j] == True) :
					print("\t1", end = "")
				else :
					print("\t-", end = "")
				
				j += 1
			
			print(end = "\n")
			i += 1
			j = 0
		
		print("\n")
	
	#  Find all paths using an active (1) key from top to bottom right
	def findPath(self, maze, track, i, j, n, m, active) :
		#  Stop process
		if (i < 0 or j < 0 or i == n or j == m or track[i][j] == True or(active == True and maze[i][j] == 1)) :
			return
		
		if (i == n - 1 and j == m - 1) :
			if ((maze[i][j] == 1 and active == False) or(maze[i][j] == 0 and active == True)) :
				#  When path contains one active key
				track[i][j] = True
				#  Display path
				self.printPath(track, n, m)
				track[i][j] = False
			
			return
		
		#  Visit element activated
		track[i][j] = True
		if (maze[i][j] == 0 or active == False) :
			status = active
			if (maze[i][j] == 1) :
				status = True
			
			#  Pick direction
			#  Down
			self.findPath(maze, track, i + 1, j, n, m, status)
			#  Right
			self.findPath(maze, track, i, j + 1, n, m, status)
			#  Left
			self.findPath(maze, track, i, j - 1, n, m, status)
			#  Top
			self.findPath(maze, track, i - 1, j, n, m, status)
		
		#  Deactivate visit element
		track[i][j] = False
	
	#  Handles the request to find active key path
	def testPath(self, maze) :
		#  Rows
		n = len(maze)
		#  Column
		m = len(maze[0])
		track = [[False] * (m) for _ in range(n) ]
		#  Find path
		self.findPath(maze, track, 0, 0, n, m, False)
	

def main() :
	task = MazePath()
	maze = [
		[0, 0, 0, 0, 0, 0] , 
        [1, 1, 0, 1, 1, 0] , 
        [1, 0, 1, 1, 1, 0] , 
        [1, 0, 0, 0, 0, 0]
	]
	task.testPath(maze)

if __name__ == "__main__": main()

Output

	1	1	-	-	-	-
	-	1	-	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	1	1	-	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	-	1	-	-	-
	-	-	1	1	1	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	1	1	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	-	1	1	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	1	1	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	-
	-	-	-	-	1	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	1	1	1
	-	-	-	-	-	1
	-	-	-	-	1	1
	-	-	-	-	1	1


#   Ruby Program for
#   Find all possible path with one magical key in maze

class MazePath 
	#  Display calculated path
	def printPath(track, n, m) 
		i = 0
		j = 0
		while (i < n) 
			while (j < m) 
				if (track[i][j] == true) 
					print("\t1")
				else 
					print("\t-")
				end

				j += 1
			end

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

		print("\n\n")
	end

	#  Find all paths using an active (1) key from top to bottom right
	def findPath(maze, track, i, j, n, m, active) 
		#  Stop process
		if (i < 0 || j < 0 || i == n || j == m || 
            track[i][j] == true || 
            (active == true && maze[i][j] == 1)) 
			return
		end

		if (i == n - 1 && j == m - 1) 
			if ((maze[i][j] == 1 && active == false) || 
                (maze[i][j] == 0 && active == true)) 
				#  When path contains one active key
				track[i][j] = true
				#  Display path
				self.printPath(track, n, m)
				track[i][j] = false
			end

			return
		end

		#  Visit element activated
		track[i][j] = true
		if (maze[i][j] == 0 || active == false) 
			status = active
			if (maze[i][j] == 1) 
				status = true
			end

			#  Pick direction
			#  Down
			self.findPath(maze, track, i + 1, j, n, m, status)
			#  Right
			self.findPath(maze, track, i, j + 1, n, m, status)
			#  Left
			self.findPath(maze, track, i, j - 1, n, m, status)
			#  Top
			self.findPath(maze, track, i - 1, j, n, m, status)
		end

		#  Deactivate visit element
		track[i][j] = false
	end

	#  Handles the request to find active key path
	def testPath(maze) 
		#  Rows
		n = maze.length
		#  Column
		m = maze[0].length
		track = Array.new(n) {Array.new(m) {false}}
		#  Find path
		self.findPath(maze, track, 0, 0, n, m, false)
	end

end

def main() 
	task = MazePath.new()
	maze = 
    [
		[0, 0, 0, 0, 0, 0] , 
        [1, 1, 0, 1, 1, 0] , 
        [1, 0, 1, 1, 1, 0] , 
        [1, 0, 0, 0, 0, 0]
	]
	task.testPath(maze)
end

main()

Output

	1	1	-	-	-	-
	-	1	-	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	1	1	-	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	-	1	-	-	-
	-	-	1	1	1	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	1	1	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	-	1	1	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	1	1	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	-
	-	-	-	-	1	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	1	1	1
	-	-	-	-	-	1
	-	-	-	-	1	1
	-	-	-	-	1	1



/*
  Scala Program for
  Find all possible path with one magical key in maze
*/
class MazePath
{
	// Display calculated path
	def printPath(track: Array[Array[Boolean]], n: Int, m: Int): Unit = {
		var i: Int = 0;
		var j: Int = 0;
		while (i < n)
		{
			while (j < m)
			{
				if (track(i)(j) == true)
				{
					print("\t1");
				}
				else
				{
					print("\t-");
				}
				j += 1;
			}
			print("\n");
			i += 1;
			j = 0;
		}
		print("\n\n");
	}
	// Find all paths using an active (1) key from top to bottom right
	def findPath(maze: Array[Array[Int]], track: Array[Array[Boolean]], 
      i: Int, j: Int, n: Int, m: Int, active: Boolean): Unit = {
		// Stop process
		if (i < 0 || j < 0 || i == n || j == m || 
             track(i)(j) == true || (active == true && maze(i)(j) == 1))
		{
			return;
		}
		if (i == n - 1 && j == m - 1)
		{
			if ((maze(i)(j) == 1 && active == false) || 
                (maze(i)(j) == 0 && active == true))
			{
				// When path contains one active key
				track(i)(j) = true;
				// Display path
				this.printPath(track, n, m);
				track(i)(j) = false;
			}
			return;
		}
		// Visit element activated
		track(i)(j) = true;
		if (maze(i)(j) == 0 || active == false)
		{
			var status: Boolean = active;
			if (maze(i)(j) == 1)
			{
				status = true;
			}
			// Pick direction
			// Down
			this.findPath(maze, track, i + 1, j, n, m, status);
			// Right
			this.findPath(maze, track, i, j + 1, n, m, status);
			// Left
			this.findPath(maze, track, i, j - 1, n, m, status);
			// Top
			this.findPath(maze, track, i - 1, j, n, m, status);
		}
		// Deactivate visit element
		track(i)(j) = false;
	}
	// Handles the request to find active key path
	def testPath(maze: Array[Array[Int]]): Unit = {
		// Rows
		var n: Int = maze.length;
		// Column
		var m: Int = maze(0).length;
		var track: Array[Array[Boolean]] = Array.fill[Boolean](n, m)(false);
		// Find path
		this.findPath(maze, track, 0, 0, n, m, false);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: MazePath = new MazePath();
		var maze: Array[Array[Int]] = Array(
          Array(0, 0, 0, 0, 0, 0), 
          Array(1, 1, 0, 1, 1, 0), 
          Array(1, 0, 1, 1, 1, 0), 
          Array(1, 0, 0, 0, 0, 0));
		task.testPath(maze);
	}
}

Output

	1	1	-	-	-	-
	-	1	-	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	1	1	-	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	-	1	-	-	-
	-	-	1	1	1	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	1	1	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	-	1	1	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	1	1	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	-
	-	-	-	-	1	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	1	1	1
	-	-	-	-	-	1
	-	-	-	-	1	1
	-	-	-	-	1	1


/*
  Swift 4 Program for
  Find all possible path with one magical key in maze
*/
class MazePath
{
	// Display calculated path
	func printPath(_ track: [[Bool]], _ n: Int, _ m: Int)
	{
		var i: Int = 0;
		var j: Int = 0;
		while (i < n)
		{
			while (j < m)
			{
				if (track[i][j] == true)
				{
					print("\t1", terminator: "");
				}
				else
				{
					print("\t-", terminator: "");
				}
				j += 1;
			}
			print(terminator: "\n");
			i += 1;
			j = 0;
		}
		print("\n");
	}
	// Find all paths using an active (1) key from top to bottom right
	func findPath(_ maze: [[Int]], _ track: inout[[Bool]], _ i: Int, _ j: Int, _ n: Int, _ m: Int, _ active: Bool)
	{
		// Stop process
		if (i < 0 || j < 0 || i == n || j == m || 
            track[i][j] == true || (active == true && maze[i][j] == 1))
		{
			return;
		}
		if (i == n - 1 && j == m - 1)
		{
			if ((maze[i][j] == 1 && active == false) || 
                (maze[i][j] == 0 && active == true))
			{
				// When path contains one active key
				track[i][j] = true;
				// Display path
				self.printPath(track, n, m);
				track[i][j] = false;
			}
			return;
		}
		// Visit element activated
		track[i][j] = true;
		if (maze[i][j] == 0 || active == false)
		{
			var status: Bool = active;
			if (maze[i][j] == 1)
			{
				status = true;
			}
			// Pick direction
			// Down
			self.findPath(maze, &track, i + 1, j, n, m, status);
			// Right
			self.findPath(maze, &track, i, j + 1, n, m, status);
			// Left
			self.findPath(maze, &track, i, j - 1, n, m, status);
			// Top
			self.findPath(maze, &track, i - 1, j, n, m, status);
		}
		// Deactivate visit element
		track[i][j] = false;
	}
	// Handles the request to find active key path
	func testPath(_ maze: [
		[Int]
	])
	{
		// Rows
		let n: Int = maze.count;
		// Column
		let m: Int = maze[0].count;
		var track: [[Bool]] = Array(repeating: Array(repeating: false, count: m), count: n);
		// Find path
		self.findPath(maze, &track, 0, 0, n, m, false);
	}
}
func main()
{
	let task: MazePath = MazePath();
	let maze: [[Int]] = 
    [
		[0, 0, 0, 0, 0, 0] , 
        [1, 1, 0, 1, 1, 0] , 
        [1, 0, 1, 1, 1, 0] , 
        [1, 0, 0, 0, 0, 0]
	];
	task.testPath(maze);
}
main();

Output

	1	1	-	-	-	-
	-	1	-	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	1	1	-	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	-	1	-	-	-
	-	-	1	1	1	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	1	1	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	-	1	1	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	1	1	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	-
	-	-	-	-	1	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	1	1	1
	-	-	-	-	-	1
	-	-	-	-	1	1
	-	-	-	-	1	1


/*
  Kotlin Program for
  Find all possible path with one magical key in maze
*/
class MazePath
{
	// Display calculated path
	fun printPath(track: Array <Array<Boolean>> , n: Int, m: Int): Unit
	{
		var i: Int = 0;
		var j: Int = 0;
		while (i < n)
		{
			while (j < m)
			{
				if (track[i][j] == true)
				{
					print("\t1");
				}
				else
				{
					print("\t-");
				}
				j += 1;
			}
			print("\n");
			i += 1;
			j = 0;
		}
		print("\n\n");
	}
	// Find all paths using an active (1) key from top to bottom right
	fun findPath(maze: Array <Array<Int>> , track: Array <Array<Boolean >> ,
                 i: Int, j: Int, n: Int, m: Int, active: Boolean): Unit
	{
		// Stop process
		if (i < 0 || j < 0 || i == n || j == m ||
            track[i][j] == true || 
            (active == true && maze[i][j] == 1))
		{
			return;
		}
		if (i == n - 1 && j == m - 1)
		{
			if ((maze[i][j] == 1 && active == false) || 
                (maze[i][j] == 0 && active == true))
			{
				// When path contains one active key
				track[i][j] = true;
				// Display path
				this.printPath(track, n, m);
				track[i][j] = false;
			}
			return;
		}
		// Visit element activated
		track[i][j] = true;
		if (maze[i][j] == 0 || active == false)
		{
			var status: Boolean = active;
			if (maze[i][j] == 1)
			{
				status = true;
			}
			// Pick direction
			// Down
			this.findPath(maze, track, i + 1, j, n, m, status);
			// Right
			this.findPath(maze, track, i, j + 1, n, m, status);
			// Left
			this.findPath(maze, track, i, j - 1, n, m, status);
			// Top
			this.findPath(maze, track, i - 1, j, n, m, status);
		}
		// Deactivate visit element
		track[i][j] = false;
	}
	// Handles the request to find active key path
	fun testPath(maze: Array<Array<Int>> ): Unit
	{
		// Rows
		var n: Int = maze.count();
		// Column
		var m: Int = maze[0].count();
		var track: Array<Array<Boolean>> = Array(n)
		{
			Array(m)
			{
				false
			}
		};
		// Find path
		this.findPath(maze, track, 0, 0, n, m, false);
	}
}
fun main(args: Array <String> ): Unit
{
	var task: MazePath = MazePath();
	var maze: Array <Array<Int>> = arrayOf(
      arrayOf(0, 0, 0, 0, 0, 0), 
      arrayOf(1, 1, 0, 1, 1, 0), 
      arrayOf(1, 0, 1, 1, 1, 0), 
      arrayOf(1, 0, 0, 0, 0, 0)
    );
	task.testPath(maze);
}

Output

	1	1	-	-	-	-
	-	1	-	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	1	1	-	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	-	1	-	-	-
	-	-	1	1	1	1


	1	1	1	-	-	-
	-	-	1	-	-	-
	-	1	1	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	1
	-	-	1	1	-	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	-	-	-
	-	1	1	-	-	-
	-	1	-	-	-	-
	-	1	1	1	1	1


	1	1	1	1	1	-
	-	-	-	-	1	1
	-	-	-	-	-	1
	-	-	-	-	-	1


	1	1	1	1	1	1
	-	-	-	-	-	1
	-	-	-	-	1	1
	-	-	-	-	1	1

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





Categories
Relative Post