# 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)
{
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}
};
}
}``````

#### 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()
{
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}
};
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)
{
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
}
};
}
}``````

#### 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()
{
\$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)
);
}
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 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]
];
}
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() :
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]
]

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()
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]
]
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));
}
}``````

#### 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 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]
];
}
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 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)
);
}``````

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