# Rat in a Maze

Given a NXN square matrix which contains 0 and 1 value. 1 indicates visible and 0 indicates invisible. Our goal is to find a path from top left corner to bottom right corner.

Here given code implementation process.

``````// C program
// Rat in a Maze

#include <stdio.h>

#define SIZE 6

//Print grid elements
void print_maze(int grid[SIZE][SIZE])
{
int i  = 0;
int j  = 0;

//Set initial values
for (i = 0; i < SIZE; ++i)
{
for (j = 0; j < SIZE; ++j)
{
printf("  %d",grid[i][j]);
}
printf("\n");
}
printf("\n");
}

//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
int solve_maze(int collection[SIZE][SIZE],int output[SIZE][SIZE],int r,int c)
{

if( r < 0 || r >= SIZE || c < 0 || c >= SIZE)
{
//When not valid position
return 0;
}
else if(r == SIZE-1 && c == SIZE-1 )
{
//When we get destination position

if(collection[r][c]==1)
{
//When destination are active element
output[r][c] = 1;

return 1;
}
}

if(output[r][c] == 1)
{
//When the element has been already been visited
return 0;
}
if(collection[r][c] == 1)
{

//Active visiting node
output[r][c] = 1;

//Test four possible direction
if(solve_maze(collection,output,r + 1, c)   ||
solve_maze(collection,output,r  , c + 1) ||
solve_maze(collection,output,r -1 , c) ||
solve_maze(collection,output,r , c - 1))
{
return 1;
}
// Deactivate visited node status
output[r][c] = 0;
}

return 0;

}
//Handles the request to find maze solution
void maze_test(int collection[SIZE][SIZE])
{
//Create resultant grid
int output[SIZE][SIZE];

int i  = 0;
int j  = 0;

//Set initial values
for (i = 0; i < SIZE; ++i)
{
for (j = 0; j < SIZE; ++j)
{
output[i][j] = 0;
}
}

if(solve_maze(collection,output,0,0))
{
//When result are exist

// Print input problem
printf("\n  Input Maze \n");
print_maze(collection);

// Display output solution
printf("\n  Output Maze \n");
print_maze(output);

}
else
{
//When no solution possible
printf("\n No Result \n");
}

}

int main()
{

int collection[SIZE][SIZE] =
{
{ 1, 0, 1, 1 ,1 ,1 },
{ 1, 1, 1, 1 ,0 ,1 },
{ 0, 1, 0, 0 ,1 ,1 },
{ 1, 0, 1, 1 ,1 ,0 },
{ 1, 0, 1, 1 ,0 ,1 },
{ 1, 0, 1, 1 ,1 ,1 }
};

maze_test(collection);
return 0;
}``````

#### Output

``````  Input Maze
1  0  1  1  1  1
1  1  1  1  0  1
0  1  0  0  1  1
1  0  1  1  1  0
1  0  1  1  0  1
1  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  0  0  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1
``````
``````/*
Java program
Rat in a Maze
*/
class Maze
{
//Print grid elements
public void print_maze(int[][] grid, int rows, int cols)
{
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
System.out.print("  " + grid[i][j] );
}
System.out.print("\n");
}
System.out.print("\n");
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
public boolean solve_maze(int[][] collection, boolean[][] output, int rows, int cols, int r, int c)
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection[r][c] == 1)
{
//When destination are active element
output[r][c] = true;
return true;
}
}
if (output[r][c] == true)
{
//When the element has been already been visited
return false;
}
if (collection[r][c] == 1)
{
//Active visiting node
output[r][c] = true;
//Test four possible direction
if (solve_maze(collection, output, rows, cols, r + 1, c)
|| solve_maze(collection, output, rows, cols, r, c + 1)
|| solve_maze(collection, output, rows, cols, r - 1, c)
|| solve_maze(collection, output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = false;
}
return false;
}
//Handles the request to find maze solution
public void maze_test(int[][] collection, int rows, int cols)
{
//Create resultant grid
boolean[][] output = new boolean[rows][cols];
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
output[i][j] = false;
}
}
if (solve_maze(collection, output, rows, cols, 0, 0))
{
//When result are exist
// Print input problem
System.out.print("\n  Input Maze \n");
print_maze(collection,rows,cols);
// Display output solution
System.out.print("  Output Maze \n");
//result
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
if( output[i][j] == false)
{
System.out.print("  0" );
}
else
{
System.out.print("  1" );
}
output[i][j] = false;
}
System.out.print("\n");
}
}
else
{
//When no solution possible
System.out.print("\n No Result \n");
}
}
public static void main(String[] args)
{
Maze obj = new Maze();
int[][] collection = {
{
1 , 0 , 1 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 0 , 1
} , {
0 , 1 , 0 , 0 , 1 , 1
} , {
1 , 0 , 1 , 1 , 1 , 0
} , {
1 , 0 , 1 , 1 , 0 , 1
} , {
1 , 0 , 1 , 1 , 1 , 1
}
};
int rows = collection.length;
int cols = collection[0].length;
obj.maze_test(collection, rows, cols);
}
}``````

#### Output

``````  Input Maze
1  0  1  1  1  1
1  1  1  1  0  1
0  1  0  0  1  1
1  0  1  1  1  0
1  0  1  1  0  1
1  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  0  0  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1``````
``````//Include header file
#include <iostream>
#define SIZE 6
using namespace std;

/*
C++ program
Rat in a Maze
*/
class Maze
{
public:
//Print grid elements
void print_maze(int grid[SIZE][SIZE], int rows, int cols)
{
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
cout << "  " << grid[i][j];
}
cout << "\n";
}
cout << "\n";
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
bool solve_maze(int collection[SIZE][SIZE], bool output[SIZE][SIZE], int rows, int cols, int r, int c)
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection[r][c] == 1)
{
//When destination are active element
output[r][c] = true;
return true;
}
}
if (output[r][c] == true)
{
//When the element has been already been visited
return false;
}
if (collection[r][c] == 1)
{
//Active visiting node
output[r][c] = true;
//Test four possible direction
if (this->solve_maze(collection, output, rows, cols, r + 1, c)
|| this->solve_maze(collection, output, rows, cols, r, c + 1)
|| this->solve_maze(collection, output, rows, cols, r - 1, c)
|| this->solve_maze(collection, output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = false;
}
return false;
}
//Handles the request to find maze solution
void maze_test(int collection[SIZE][SIZE], int rows, int cols)
{
//Create resultant grid
bool output[SIZE][SIZE];
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
output[i][j] = false;
}
}
if (this->solve_maze(collection, output, rows, cols, 0, 0)==true)
{
//When result are exist
// Print input problem
cout << "\n  Input Maze \n";
this->print_maze(collection, rows, cols);
// Display output solution
cout << "  Output Maze \n";
//result
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
if (output[i][j] == false)
{
cout << "  0";
}
else
{
cout << "  1";
}
output[i][j] = false;
}
cout << "\n";
}
}
else
{
//When no solution possible
cout << "\n No Result \n";
}
}
};
int main()
{
Maze obj = Maze();
int collection[SIZE][SIZE] = {
{
1 , 0 , 1 , 1 , 1 , 1
} ,
{
1 , 1 , 1 , 1 , 0 , 1
} ,
{
0 , 1 , 0 , 0 , 1 , 1
} ,
{
1 , 0 , 1 , 1 , 1 , 0
} ,
{
1 , 0 , 1 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 1 , 1 , 1
}
};
int rows = sizeof(collection) / sizeof(collection[0]);
int cols = sizeof(collection[0]) / sizeof(collection[0][0]);
obj.maze_test(collection, rows, cols);
return 0;
}``````

#### Output

``````  Input Maze
1  0  1  1  1  1
1  1  1  1  0  1
0  1  0  0  1  1
1  0  1  1  1  0
1  0  1  1  0  1
1  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  0  0  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1``````
``````//Include namespace system
using System;
/*
C# program
Rat in a Maze
*/
class Maze
{
//Print grid elements
public void print_maze(int[,] grid, int rows, int cols)
{
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
Console.Write("  " + grid[i,j]);
}
Console.Write("\n");
}
Console.Write("\n");
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
public Boolean solve_maze(int[,] collection, Boolean[,] output, int rows, int cols, int r, int c)
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection[r,c] == 1)
{
//When destination are active element
output[r,c] = true;
return true;
}
}
if (output[r,c] == true)
{
//When the element has been already been visited
return false;
}
if (collection[r,c] == 1)
{
//Active visiting node
output[r,c] = true;
//Test four possible direction
if (solve_maze(collection, output, rows, cols, r + 1, c) || solve_maze(collection, output, rows, cols, r, c + 1) || solve_maze(collection, output, rows, cols, r - 1, c) || solve_maze(collection, output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output[r,c] = false;
}
return false;
}
//Handles the request to find maze solution
public void maze_test(int[,] collection, int rows, int cols)
{
//Create resultant grid
Boolean[,] output = new Boolean[rows,cols];
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
output[i,j] = false;
}
}
if (solve_maze(collection, output, rows, cols, 0, 0))
{
//When result are exist
// Print input problem
Console.Write("\n  Input Maze \n");
print_maze(collection, rows, cols);
// Display output solution
Console.Write("  Output Maze \n");
//result
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
if (output[i,j] == false)
{
Console.Write("  0");
}
else
{
Console.Write("  1");
}
output[i,j] = false;
}
Console.Write("\n");
}
}
else
{
//When no solution possible
Console.Write("\n No Result \n");
}
}
public static void Main(String[] args)
{
Maze obj = new Maze();
int[,] collection = {
{
1 , 0 , 1 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 0 , 1
} , {
0 , 1 , 0 , 0 , 1 , 1
} , {
1 , 0 , 1 , 1 , 1 , 0
} , {
1 , 0 , 1 , 1 , 0 , 1
} , {
1 , 0 , 1 , 1 , 1 , 1
}
};
int rows = collection.GetLength(0);
int cols = collection.GetLength(1);
obj.maze_test(collection, rows, cols);
}
}``````

#### Output

``````  Input Maze
1  0  1  1  1  1
1  1  1  1  0  1
0  1  0  0  1  1
1  0  1  1  1  0
1  0  1  1  0  1
1  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  0  0  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1``````
``````<?php
/*
Php program
Rat in a Maze
*/
class Maze
{
//Print grid elements
public  function print_maze( & \$grid, \$rows, \$cols)
{
\$i = 0;
\$j = 0;
//Set initial values
while (\$i < \$rows)
{
\$j = 0;
while (\$j < \$cols)
{
echo "  ". \$grid[\$i][\$j];
++\$j;
}
echo "\n";
++\$i;
}
echo "\n";
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
public  function solve_maze( & \$collection, & \$output, \$rows, \$cols, \$r, \$c)
{
if (\$r < 0 || \$r >= \$rows || \$c < 0 || \$c >= \$cols)
{
//When not valid position
return false;
}
else if (\$r == \$rows - 1 && \$c == \$cols - 1)
{
//When we get destination position
if (\$collection[\$r][\$c] == 1)
{
//When destination are active element
\$output[\$r][\$c] = true;
return true;
}
}
if (\$output[\$r][\$c] == true)
{
//When the element has been already been visited
return false;
}
if (\$collection[\$r][\$c] == 1)
{
//Active visiting node
\$output[\$r][\$c] = true;
//Test four possible direction
if (\$this->solve_maze(\$collection, \$output, \$rows, \$cols, \$r + 1, \$c) || \$this->solve_maze(\$collection, \$output, \$rows, \$cols, \$r, \$c + 1) || \$this->solve_maze(\$collection, \$output, \$rows, \$cols, \$r - 1, \$c) || \$this->solve_maze(\$collection, \$output, \$rows, \$cols, \$r, \$c - 1))
{
return true;
}
// Deactivate visited node status
\$output[\$r][\$c] = false;
}
return false;
}
//Handles the request to find maze solution
public  function maze_test( & \$collection, \$rows, \$cols)
{
//Create resultant grid
\$output = array_fill(0, \$rows, array_fill(0, \$cols, false));
\$i = 0;
\$j = 0;
if (\$this->solve_maze(\$collection, \$output, \$rows, \$cols, 0, 0))
{
//When result are exist
// Print input problem
echo "\n  Input Maze \n";
\$this->print_maze(\$collection, \$rows, \$cols);
// Display output solution
echo "  Output Maze \n";
//result
\$i = 0;
while (\$i < \$rows)
{
\$j = 0;
while (\$j < \$cols)
{
if (\$output[\$i][\$j] == false)
{
echo "  0";
}
else
{
echo "  1";
}
\$output[\$i][\$j] = false;
++\$j;
}
echo "\n";
++\$i;
}
}
else
{
//When no solution possible
echo "\n No Result \n";
}
}
}

function main()
{
\$obj = new Maze();
\$collection = array(array(1, 0, 1, 1, 1, 1),
array(1, 1, 1, 1, 0, 1),
array(0, 1, 0, 0, 1, 1),
array(1, 0, 1, 1, 1, 0),
array(1, 0, 1, 1, 0, 1),
array(1, 0, 1, 1, 1, 1));
\$rows = count(\$collection);
\$cols = count(\$collection[0]);
\$obj->maze_test(\$collection, \$rows, \$cols);
}
main();``````

#### Output

``````  Input Maze
1  0  1  1  1  1
1  1  1  1  0  1
0  1  0  0  1  1
1  0  1  1  1  0
1  0  1  1  0  1
1  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  0  0  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1``````
``````/*
Node Js program
Rat in a Maze
*/
class Maze
{
//Print grid elements
print_maze(grid, rows, cols)
{
var i = 0;
var j = 0;
//Set initial values
while (i < rows)
{
j = 0;
while (j < cols)
{
process.stdout.write("  " + grid[i][j]);
++j;
}
process.stdout.write("\n");
++i;
}
process.stdout.write("\n");
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
solve_maze(collection, output, rows, cols, r, c)
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection[r][c] == 1)
{
//When destination are active element
output[r][c] = true;
return true;
}
}
if (output[r][c] == true)
{
//When the element has been already been visited
return false;
}
if (collection[r][c] == 1)
{
//Active visiting node
output[r][c] = true;
//Test four possible direction
if (this.solve_maze(collection, output, rows, cols, r + 1, c) || this.solve_maze(collection, output, rows, cols, r, c + 1) || this.solve_maze(collection, output, rows, cols, r - 1, c) || this.solve_maze(collection, output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = false;
}
return false;
}
//Handles the request to find maze solution
maze_test(collection, rows, cols)
{
//Create resultant grid
var output = Array(rows).fill(false).map(() => new Array(cols).fill(false));
var i = 0;
var j = 0;
if (this.solve_maze(collection, output, rows, cols, 0, 0))
{
//When result are exist
// Print input problem
process.stdout.write("\n  Input Maze \n");
this.print_maze(collection, rows, cols);
// Display output solution
process.stdout.write("  Output Maze \n");
//result
i = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
if (output[i][j] == false)
{
process.stdout.write("  0");
}
else
{
process.stdout.write("  1");
}
output[i][j] = false;
++j;
}
process.stdout.write("\n");
++i;
}
}
else
{
//When no solution possible
process.stdout.write("\n No Result \n");
}
}
}

function main()
{
var obj = new Maze();
var collection = [
[1, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 1, 0],
[1, 0, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 1]
];
var rows = collection.length;
var cols = collection[0].length;
obj.maze_test(collection, rows, cols);
}
main();``````

#### Output

``````  Input Maze
1  0  1  1  1  1
1  1  1  1  0  1
0  1  0  0  1  1
1  0  1  1  1  0
1  0  1  1  0  1
1  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  0  0  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1``````
``````#   Python 3 program
#   Rat in a Maze

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

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

print("\n", end = "")

# Using backtracking find maze solution
# If solutions are not exist then it returns 0 (False).
def solve_maze(self, collection, output, rows, cols, r, c) :
if (r < 0 or r >= rows or c < 0 or c >= cols) :
# When not valid position
return False

elif(r == rows - 1 and c == cols - 1) :
# When we get destination position
if (collection[r][c] == 1) :
# When destination are active element
output[r][c] = True
return True

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

if (collection[r][c] == 1) :
# Active visiting node
output[r][c] = True
# Test four possible direction
if (self.solve_maze(collection, output, rows, cols, r + 1, c) or self.solve_maze(collection, output, rows, cols, r, c + 1) or self.solve_maze(collection, output, rows, cols, r - 1, c) or self.solve_maze(collection, output, rows, cols, r, c - 1)) :
return True

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

return False

# Handles the request to find maze solution
def maze_test(self, collection, rows, cols) :
# Create resultant grid
output = [[False] * (cols) for _ in range(rows) ]
i = 0
j = 0
if (self.solve_maze(collection, output, rows, cols, 0, 0)) :
# When result are exist
#  Print input problem
print("\n  Input Maze \n", end = "")
self.print_maze(collection, rows, cols)
#  Display output solution
print("  Output Maze \n", end = "")
# result
i = 0
while (i < rows) :
j = 0
while (j < cols) :
if (output[i][j] == False) :
print("   0", end = "")
else :
print("   1", end = "")

output[i][j] = False
j += 1

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

else :
# When no solution possible
print("\n No Result \n", end = "")

def main() :
obj = Maze()
collection = [
[1, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 1, 0],
[1, 0, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 1]
]
rows = len(collection)
cols = len(collection[0])
obj.maze_test(collection, rows, cols)

if __name__ == "__main__": main()``````

#### Output

``````  Input Maze
1   0   1   1   1   1
1   1   1   1   0   1
0   1   0   0   1   1
1   0   1   1   1   0
1   0   1   1   0   1
1   0   1   1   1   1

Output Maze
1   0   0   1   1   1
1   1   1   1   0   1
0   0   0   0   1   1
0   0   0   1   1   0
0   0   0   1   0   0
0   0   0   1   1   1``````
``````#   Ruby program
#   Rat in a Maze

class Maze
# Print grid elements
def print_maze(grid, rows, cols)
i = 0
j = 0
# Set initial values
while (i < rows)
j = 0
while (j < cols)
print("  ", grid[i][j])
j += 1
end

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

print("\n")
end

# Using backtracking find maze solution
# If solutions are not exist then it returns 0 (False).
def solve_maze(collection, output, rows, cols, r, c)
if (r < 0 || r >= rows || c < 0 || c >= cols)
# When not valid position
return false
elsif(r == rows - 1 && c == cols - 1)
# When we get destination position
if (collection[r][c] == 1)
# When destination are active element
output[r][c] = true
return true
end

end

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

if (collection[r][c] == 1)
# Active visiting node
output[r][c] = true
# Test four possible direction
if (self.solve_maze(collection, output, rows, cols, r + 1, c) || self.solve_maze(collection, output, rows, cols, r, c + 1) || self.solve_maze(collection, output, rows, cols, r - 1, c) || self.solve_maze(collection, output, rows, cols, r, c - 1))
return true
end

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

return false
end

# Handles the request to find maze solution
def maze_test(collection, rows, cols)
# Create resultant grid
output = Array.new(rows) {Array.new(cols) {false}}
i = 0
j = 0
if (self.solve_maze(collection, output, rows, cols, 0, 0))
# When result are exist
#  Print input problem
print("\n  Input Maze \n")
self.print_maze(collection, rows, cols)
#  Display output solution
print("  Output Maze \n")
# result
i = 0
while (i < rows)
j = 0
while (j < cols)
if (output[i][j] == false)
print("  0")
else
print("  1")
end

output[i][j] = false
j += 1
end

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

else
# When no solution possible
print("\n No Result \n")
end

end

end

def main()
obj = Maze.new()
collection = [
[1, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 1, 0],
[1, 0, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 1]
]
rows = collection.length
cols = collection[0].length
obj.maze_test(collection, rows, cols)
end

main()``````

#### Output

``````  Input Maze
1  0  1  1  1  1
1  1  1  1  0  1
0  1  0  0  1  1
1  0  1  1  1  0
1  0  1  1  0  1
1  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  0  0  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1
``````
``````/*
Scala program
Rat in a Maze
*/
class Maze
{
//Print grid elements
def print_maze(grid: Array[Array[Int]],
rows: Int, cols: Int): Unit = {
var i: Int = 0;
var j: Int = 0;
//Set initial values
while (i < rows)
{
j = 0;
while (j < cols)
{
print("  " + grid(i)(j));
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
def solve_maze(collection: Array[Array[Int]],
output: Array[Array[Boolean]],
rows: Int, cols: Int, r: Int, c: Int): Boolean = {
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection(r)(c) == 1)
{
//When destination are active element
output(r)(c) = true;
return true;
}
}
if (output(r)(c) == true)
{
//When the element has been already been visited
return false;
}
if (collection(r)(c) == 1)
{
//Active visiting node
output(r)(c) = true;
//Test four possible direction
if (solve_maze(collection, output, rows, cols, r + 1, c)
|| solve_maze(collection, output, rows, cols, r, c + 1)
|| solve_maze(collection, output, rows, cols, r - 1, c)
|| solve_maze(collection, output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output(r)(c) = false;
}
return false;
}
//Handles the request to find maze solution
def maze_test(collection: Array[Array[Int]], rows: Int, cols: Int): Unit = {
//Create resultant grid
var output: Array[Array[Boolean]] = Array.fill[Boolean](rows, cols)(false);
var i: Int = 0;
var j: Int = 0;

if (solve_maze(collection, output, rows, cols, 0, 0))
{
//When result are exist
// Print input problem
print("\n  Input Maze \n");
print_maze(collection, rows, cols);
// Display output solution
print("  Output Maze \n");
//result
i = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
if (output(i)(j) == false)
{
print("  0");
}
else
{
print("  1");
}
output(i)(j) = false;
j += 1;
}
print("\n");
i += 1;
}
}
else
{
//When no solution possible
print("\n No Result \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: Maze = new Maze();
var collection: Array[Array[Int]] = Array(Array(1, 0, 1, 1, 1, 1), Array(1, 1, 1, 1, 0, 1), Array(0, 1, 0, 0, 1, 1), Array(1, 0, 1, 1, 1, 0), Array(1, 0, 1, 1, 0, 1), Array(1, 0, 1, 1, 1, 1));
var rows: Int = collection.length;
var cols: Int = collection(0).length;
obj.maze_test(collection, rows, cols);
}
}``````

#### Output

``````  Input Maze
1  0  1  1  1  1
1  1  1  1  0  1
0  1  0  0  1  1
1  0  1  1  1  0
1  0  1  1  0  1
1  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  0  0  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1``````
``````/*
Swift 4 program
Rat in a Maze
*/
class Maze
{
//Print grid elements
func print_maze(_ grid: [[Int]], _ rows: Int, _ cols: Int)
{
var i: Int = 0;
var j: Int = 0;
//Set initial values
while (i < rows)
{
j = 0;
while (j < cols)
{
print("  ", grid[i][j], terminator: "");
j += 1;
}
print("\n", terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
func solve_maze(_ collection: [[Int]], _ output: inout[[Bool]], _ rows: Int, _ cols: Int, _ r: Int, _ c: Int) -> Bool
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection[r][c] == 1)
{
//When destination are active element
output[r][c] = true;
return true;
}
}
if (output[r][c] == true)
{
//When the element has been already been visited
return false;
}
if (collection[r][c] == 1)
{
//Active visiting node
output[r][c] = true;
//Test four possible direction
if (self.solve_maze(collection, &output, rows, cols, r + 1, c)
|| self.solve_maze(collection, &output, rows, cols, r, c + 1)
|| self.solve_maze(collection, &output, rows, cols, r - 1, c)
|| self.solve_maze(collection, &output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = false;
}
return false;
}
//Handles the request to find maze solution
func maze_test(_ collection: [[Int]], _ rows: Int, _ cols: Int)
{
//Create resultant grid
var output: [[Bool]] = Array(repeating: Array(repeating: false, count: cols), count: rows);
var i: Int = 0;
var j: Int = 0;
if (self.solve_maze(collection, &output, rows, cols, 0, 0))
{
//When result are exist
// Print input problem
print("\n  Input Maze \n", terminator: "");
self.print_maze(collection, rows, cols);
// Display output solution
print("  Output Maze \n", terminator: "");
//result
i = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
if (output[i][j] == false)
{
print("   0", terminator: "");
}
else
{
print("   1", terminator: "");
}
output[i][j] = false;
j += 1;
}
print("\n", terminator: "");
i += 1;
}
}
else
{
//When no solution possible
print("\n No Result \n", terminator: "");
}
}
}
func main()
{
let obj: Maze = Maze();
let collection: [[Int]] = [[1, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 1, 0],
[1, 0, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 1]];
let rows: Int = collection.count;
let cols: Int = collection[0].count;
obj.maze_test(collection, rows, cols);
}
main();``````

#### Output

``````  Input Maze
1   0   1   1   1   1
1   1   1   1   0   1
0   1   0   0   1   1
1   0   1   1   1   0
1   0   1   1   0   1
1   0   1   1   1   1

Output Maze
1   0   0   1   1   1
1   1   1   1   0   1
0   0   0   0   1   1
0   0   0   1   1   0
0   0   0   1   0   0
0   0   0   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.