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