Find paths from corner cell to middle cell in maze
Here given code implementation process.
/*
Java Program for
Find paths from corner cell to middle cell in maze
*/
public class Path
{
public boolean status;
public Path()
{
this.status = false;
}
public void display(int[][] maze, int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
System.out.print(" " + maze[i][j]);
}
}
System.out.print("\n");
}
public void printPath(int[][] maze, int i, int j, int mid, String result)
{
if (i == mid && j == mid)
{
// When we get middle row and middle column
this.status = true;
System.out.println(result + "(MID[" + i + "][" + j + "]) ");
return;
}
if (maze[i][j] == 0)
{
return;
}
int value = maze[i][j];
maze[i][j] = 0;
if (j + value < maze.length)
{
// Move right
printPath(maze, i, j + value, mid, result + "[" + i + "][" + j + "]⤑ ");
}
if (i + value < maze.length)
{
// Move down
printPath(maze, i + value, j, mid, result + "[" + i + "][" + j + "]⤑ ");
}
if (j - value > 0)
{
// Move left
printPath(maze, i, j - value, mid, result + "[" + i + "][" + j + "]⤑ ");
}
if (i - value > 0)
{
// Move Up
printPath(maze, i - value, j, mid, result + "[" + i + "][" + j + "]⤑ ");
}
maze[i][j] = value;
}
void printSolution(int[][] maze)
{
int n = maze.length;
this.status = false;
// Find path
printPath(maze, 0, 0, n / 2, "");
if (this.status == false)
{
// No solution
System.out.println("\n No result ");
}
}
public static void main(String[] args)
{
Path task = new Path();
// Odd square matrix
int[][] maze = {
{
3 , 1 , 4 , 2 , 3
},
{
3 , 2 , 2 , 1 , 3
},
{
1 , 3 , 4 , 3 , 2
},
{
2 , 3 , 1 , 1 , 2
},
{
4 , 2 , 4 , 3 , 0 ,
}
};
/*
maze =
[
[ 3, 1, 4, 2, 3 ]
[ 3, 2, 2, 1, 3 ]
[ 1, 3, 4, 3, 2 ]
[ 2, 3, 1, 1, 2 ]
[ 4, 2, 4, 3, 0,]
]
------------------------
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, 2, 1, - ]
[ -, 3, 4, 3, - ]
[ -, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➀
[0][0] ⤑ [0][3] ⤑ [0][1] ⤑ [1][1] ⤑
[1][3] ⤑ [1][2] ⤑ [3][2] ⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, -, -, - ]
[ -, -, 4, -, - ]
[ -, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➁
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑
[3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ -, -, -, -, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➂
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, -, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➃
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, 2, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➄
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, -, 2, 1, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➅
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
*/
task.printSolution(maze);
}
}
Output
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
// Include header file
#include <iostream>
#include <string>
#define N 5
using namespace std;
/*
C++ Program for
Find paths from corner cell to middle cell in maze
*/
class Path
{
public: bool status;
Path()
{
this->status = false;
}
void display(int maze[N][N])
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
cout << " " << maze[i][j];
}
}
cout << "\n";
}
void printPath(int maze[N][N], int i, int j, int mid, string result)
{
if (i == mid && j == mid)
{
// When we get middle row and middle column
this->status = true;
cout << result << "(MID[" << i << "][" << j << "]) " << endl;
return;
}
if (maze[i][j] == 0)
{
return;
}
int value = maze[i][j];
maze[i][j] = 0;
if (j + value < N)
{
// Move right
this->printPath(maze, i, j + value, mid,
result + "[" + to_string(i) + "][" + to_string(j) + "]⤑ ");
}
if (i + value < N)
{
// Move down
this->printPath(maze, i + value, j, mid,
result + "[" + to_string(i) + "][" + to_string(j) + "]⤑ ");
}
if (j - value > 0)
{
// Move left
this->printPath(maze, i, j - value, mid,
result + "[" + to_string(i) + "][" + to_string(j) + "]⤑ ");
}
if (i - value > 0)
{
// Move Up
this->printPath(maze, i - value, j, mid,
result + "[" + to_string(i) + "][" + to_string(j) + "]⤑ ");
}
maze[i][j] = value;
}
void printSolution(int maze[N][N])
{
this->status = false;
this->printPath(maze, 0, 0, N / 2, "");
if (this->status == false)
{
// No solution
cout << "\n No result " << endl;
}
}
};
int main()
{
Path *task = new Path();
// Odd square matrix
int maze[N][N] = {
{
3 , 1 , 4 , 2 , 3
} , {
3 , 2 , 2 , 1 , 3
} , {
1 , 3 , 4 , 3 , 2
} , {
2 , 3 , 1 , 1 , 2
} , {
4 , 2 , 4 , 3 , 0
}
};
/*
maze =
[
[ 3, 1, 4, 2, 3 ]
[ 3, 2, 2, 1, 3 ]
[ 1, 3, 4, 3, 2 ]
[ 2, 3, 1, 1, 2 ]
[ 4, 2, 4, 3, 0,]
]
------------------------
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, 2, 1, - ]
[ -, 3, 4, 3, - ]
[ -, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➀
[0][0] ⤑ [0][3] ⤑ [0][1] ⤑ [1][1] ⤑
[1][3] ⤑ [1][2] ⤑ [3][2] ⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, -, -, - ]
[ -, -, 4, -, - ]
[ -, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➁
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑
[3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ -, -, -, -, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➂
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, -, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➃
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, 2, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➄
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, -, 2, 1, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➅
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
*/
task->printSolution(maze);
return 0;
}
Output
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
// Include namespace system
using System;
/*
Csharp Program for
Find paths from corner cell to middle cell in maze
*/
public class Path
{
public Boolean status;
public Path()
{
this.status = false;
}
public void display(int[,] maze, int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
Console.Write(" " + maze[i,j]);
}
}
Console.Write("\n");
}
public void printPath(int[,] maze,
int i, int j,
int mid, String result)
{
if (i == mid && j == mid)
{
// When we get middle row and middle column
this.status = true;
Console.WriteLine(result + "(MID[" + i + "," + j + "]) ");
return;
}
if (maze[i,j] == 0)
{
return;
}
int value = maze[i,j];
maze[i,j] = 0;
if (j + value < maze.GetLength(0))
{
// Move right
this.printPath(maze, i, j + value,
mid, result + "[" + i + "," + j + "]⤑ ");
}
if (i + value < maze.GetLength(0))
{
// Move down
this.printPath(maze, i + value, j,
mid, result + "[" + i + "," + j + "]⤑ ");
}
if (j - value > 0)
{
// Move left
this.printPath(maze, i, j - value,
mid, result + "[" + i + "," + j + "]⤑ ");
}
if (i - value > 0)
{
// Move Up
this.printPath(maze, i - value, j,
mid, result + "[" + i + "," + j + "]⤑ ");
}
maze[i,j] = value;
}
void printSolution(int[,] maze)
{
int n = maze.GetLength(0);
this.status = false;
this.printPath(maze, 0, 0, n / 2, "");
if (this.status == false)
{
// No solution
Console.WriteLine("\n No result ");
}
}
public static void Main(String[] args)
{
Path task = new Path();
// Odd square matrix
int[,] maze = {
{
3 , 1 , 4 , 2 , 3
},
{
3 , 2 , 2 , 1 , 3
},
{
1 , 3 , 4 , 3 , 2
},
{
2 , 3 , 1 , 1 , 2
},
{
4 , 2 , 4 , 3 , 0
}
};
/*
maze =
[
[ 3, 1, 4, 2, 3 ]
[ 3, 2, 2, 1, 3 ]
[ 1, 3, 4, 3, 2 ]
[ 2, 3, 1, 1, 2 ]
[ 4, 2, 4, 3, 0,]
]
------------------------
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, 2, 1, - ]
[ -, 3, 4, 3, - ]
[ -, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➀
[0,0] ⤑ [0,3] ⤑ [0,1] ⤑ [1,1] ⤑
[1,3] ⤑ [1,2] ⤑ [3,2] ⤑ (MID[2,2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, -, -, - ]
[ -, -, 4, -, - ]
[ -, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➁
[0,0]⤑ [0,3]⤑ [0,1]⤑ [1,1]⤑ [3,1]⤑
[3,4]⤑ [3,2]⤑ (MID[2,2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ -, -, -, -, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➂
[0,0]⤑ [3,0]⤑ [3,2]⤑ (MID[2,2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, -, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➃
[0,0]⤑ [3,0]⤑ [1,0]⤑ [1,3]⤑ [1,4]⤑
[1,1]⤑ [3,1]⤑ [3,4]⤑ [3,2]⤑ (MID[2,2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, 2, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➄
[0,0]⤑ [3,0]⤑ [1,0]⤑ [1,3]⤑ [1,2]⤑ [1,4]⤑
[1,1]⤑ [3,1]⤑ [3,4]⤑ [3,2]⤑ (MID[2,2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, -, 2, 1, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➅
[0,0]⤑ [3,0]⤑ [1,0]⤑ [1,3]⤑ [1,2]⤑ [3,2]⤑ (MID[2,2])
*/
task.printSolution(maze);
}
}
Output
[0,0]⤑ [0,3]⤑ [0,1]⤑ [1,1]⤑ [1,3]⤑ [1,2]⤑ [3,2]⤑ (MID[2,2])
[0,0]⤑ [0,3]⤑ [0,1]⤑ [1,1]⤑ [3,1]⤑ [3,4]⤑ [3,2]⤑ (MID[2,2])
[0,0]⤑ [3,0]⤑ [3,2]⤑ (MID[2,2])
[0,0]⤑ [3,0]⤑ [1,0]⤑ [1,3]⤑ [1,4]⤑ [1,1]⤑ [3,1]⤑ [3,4]⤑ [3,2]⤑ (MID[2,2])
[0,0]⤑ [3,0]⤑ [1,0]⤑ [1,3]⤑ [1,2]⤑ [1,4]⤑ [1,1]⤑ [3,1]⤑ [3,4]⤑ [3,2]⤑ (MID[2,2])
[0,0]⤑ [3,0]⤑ [1,0]⤑ [1,3]⤑ [1,2]⤑ [3,2]⤑ (MID[2,2])
package main
import "strconv"
import "fmt"
/*
Go Program for
Find paths from corner cell to middle cell in maze
*/
type Path struct {
status bool
}
func getPath() * Path {
var me *Path = &Path {}
me.status = false
return me
}
func(this Path) display(maze[][] int, n int) {
for i := 0 ; i < n ; i++ {
for j := 0 ; j < n ; j++ {
fmt.Print(" ", maze[i][j])
}
}
fmt.Print("\n")
}
func(this *Path) printPath(maze[][] int, i int, j int, mid int, result string) {
if i == mid && j == mid {
// When we get middle row and middle column
this.status = true
fmt.Println(result, "(MID[", i, "][", j, "]) ")
return
}
if maze[i][j] == 0 {
return
}
var value int = maze[i][j]
maze[i][j] = 0
if j + value < len(maze) {
// Move right
this.printPath(maze, i, j + value, mid, result + "[" +
strconv.Itoa(i) + "][" +
strconv.Itoa(j) + "]⤑ ")
}
if i + value < len(maze) {
// Move down
this.printPath(maze, i + value, j, mid, result + "[" +
strconv.Itoa(i) + "][" +
strconv.Itoa(j) + "]⤑ ")
}
if j - value > 0 {
// Move left
this.printPath(maze, i, j - value, mid, result + "[" +
strconv.Itoa(i) + "][" +
strconv.Itoa(j) + "]⤑ ")
}
if i - value > 0 {
// Move Up
this.printPath(maze, i - value, j, mid, result + "[" +
strconv.Itoa(i) + "][" +
strconv.Itoa(j) + "]⤑ ")
}
maze[i][j] = value
}
func(this Path) printSolution(maze[][] int) {
var n int = len(maze)
this.status = false
this.printPath(maze, 0, 0, n / 2, "")
if this.status == false {
// No solution
fmt.Println("\n No result ")
}
}
func main() {
var task * Path = getPath()
// Odd square matrix
var maze = [][] int {
{ 3 , 1 , 4 , 2 , 3 } ,
{ 3 , 2 , 2 , 1 , 3 } ,
{ 1 , 3 , 4 , 3 , 2 } ,
{ 2 , 3 , 1 , 1 , 2 } ,
{ 4 , 2 , 4 , 3 , 0 }}
/*
maze =
[
[ 3, 1, 4, 2, 3 ]
[ 3, 2, 2, 1, 3 ]
[ 1, 3, 4, 3, 2 ]
[ 2, 3, 1, 1, 2 ]
[ 4, 2, 4, 3, 0,]
]
------------------------
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, 2, 1, - ]
[ -, 3, 4, 3, - ]
[ -, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➀
[0][0] ⤑ [0][3] ⤑ [0][1] ⤑ [1][1] ⤑
[1][3] ⤑ [1][2] ⤑ [3][2] ⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, -, -, - ]
[ -, -, 4, -, - ]
[ -, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➁
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑
[3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ -, -, -, -, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➂
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, -, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➃
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, 2, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➄
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, -, 2, 1, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➅
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
*/
task.printSolution(maze)
}
Output
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
<?php
/*
Php Program for
Find paths from corner cell to middle cell in maze
*/
class Path
{
public $status;
public function __construct()
{
$this->status = false;
}
public function display($maze, $n)
{
for ($i = 0; $i < $n; ++$i)
{
for ($j = 0; $j < $n; ++$j)
{
echo(" ".$maze[$i][$j]);
}
}
echo("\n");
}
public function printPath($maze, $i, $j, $mid, $result)
{
if ($i == $mid && $j == $mid)
{
// When we get middle row and middle column
$this->status = true;
echo($result."(MID[".$i."][".$j."]) \n");
return;
}
if ($maze[$i][$j] == 0)
{
return;
}
$value = $maze[$i][$j];
$maze[$i][$j] = 0;
if ($j + $value < count($maze))
{
// Move right
$this->printPath($maze, $i, $j + $value, $mid,
$result."[".strval($i)."][".strval($j)."]⤑ ");
}
if ($i + $value < count($maze))
{
// Move down
$this->printPath($maze, $i + $value, $j, $mid,
$result."[".strval($i)."][".strval($j)."]⤑ ");
}
if ($j - $value > 0)
{
// Move left
$this->printPath($maze, $i, $j - $value, $mid,
$result."[".strval($i)."][".strval($j)."]⤑ ");
}
if ($i - $value > 0)
{
// Move Up
$this->printPath($maze, $i - $value, $j, $mid,
$result."[".strval($i)."][".strval($j)."]⤑ ");
}
$maze[$i][$j] = $value;
}
function printSolution($maze)
{
$n = count($maze);
$this->status = false;
$this->printPath($maze, 0, 0, (int)($n / 2), "");
if ($this->status == false)
{
// No solution
echo("\n No result ".
"\n");
}
}
}
function main()
{
$task = new Path();
// Odd square matrix
$maze = array(array(3, 1, 4, 2, 3), array(3, 2, 2, 1, 3), array(1, 3, 4, 3, 2), array(2, 3, 1, 1, 2), array(4, 2, 4, 3, 0));
/*
maze =
[
[ 3, 1, 4, 2, 3 ]
[ 3, 2, 2, 1, 3 ]
[ 1, 3, 4, 3, 2 ]
[ 2, 3, 1, 1, 2 ]
[ 4, 2, 4, 3, 0,]
]
------------------------
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, 2, 1, - ]
[ -, 3, 4, 3, - ]
[ -, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➀
[0][0] ⤑ [0][3] ⤑ [0][1] ⤑ [1][1] ⤑
[1][3] ⤑ [1][2] ⤑ [3][2] ⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, -, -, - ]
[ -, -, 4, -, - ]
[ -, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➁
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑
[3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ -, -, -, -, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➂
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, -, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➃
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, 2, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➄
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, -, 2, 1, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➅
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
*/
$task->printSolution($maze);
}
main();
Output
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
/*
Node JS Program for
Find paths from corner cell to middle cell in maze
*/
class Path
{
constructor()
{
this.status = false;
}
display(maze, n)
{
for (var i = 0; i < n; ++i)
{
for (var j = 0; j < n; ++j)
{
process.stdout.write(" " + maze[i][j]);
}
}
process.stdout.write("\n");
}
printPath(maze, i, j, mid, result)
{
if (i == mid && j == mid)
{
// When we get middle row and middle column
this.status = true;
console.log(result + "(MID[" + i + "][" + j + "]) ");
return;
}
if (maze[i][j] == 0)
{
return;
}
var value = maze[i][j];
maze[i][j] = 0;
if (j + value < maze.length)
{
// Move right
this.printPath(maze, i, j + value,
mid, result + "[" + i + "][" + j + "]⤑ ");
}
if (i + value < maze.length)
{
// Move down
this.printPath(maze, i + value, j,
mid, result + "[" + i + "][" + j + "]⤑ ");
}
if (j - value > 0)
{
// Move left
this.printPath(maze, i, j - value,
mid, result + "[" + i + "][" + j + "]⤑ ");
}
if (i - value > 0)
{
// Move Up
this.printPath(maze, i - value, j,
mid, result + "[" + i + "][" + j + "]⤑ ");
}
maze[i][j] = value;
}
printSolution(maze)
{
var n = maze.length;
this.status = false;
this.printPath(maze, 0, 0, parseInt(n / 2), "");
if (this.status == false)
{
// No solution
console.log("\n No result ");
}
}
}
function main()
{
var task = new Path();
// Odd square matrix
var maze = [
[3, 1, 4, 2, 3],
[3, 2, 2, 1, 3],
[1, 3, 4, 3, 2],
[2, 3, 1, 1, 2],
[4, 2, 4, 3, 0]
];
/*
maze =
[
[ 3, 1, 4, 2, 3 ]
[ 3, 2, 2, 1, 3 ]
[ 1, 3, 4, 3, 2 ]
[ 2, 3, 1, 1, 2 ]
[ 4, 2, 4, 3, 0,]
]
------------------------
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, 2, 1, - ]
[ -, 3, 4, 3, - ]
[ -, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➀
[0][0] ⤑ [0][3] ⤑ [0][1] ⤑ [1][1] ⤑
[1][3] ⤑ [1][2] ⤑ [3][2] ⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, -, -, - ]
[ -, -, 4, -, - ]
[ -, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➁
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑
[3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ -, -, -, -, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➂
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, -, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➃
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, 2, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➄
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, -, 2, 1, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➅
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
*/
task.printSolution(maze);
}
main();
Output
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
# Python 3 Program for
# Find paths from corner cell to middle cell in maze
class Path :
def __init__(self) :
self.status = False
def display(self, maze, n) :
i = 0
while (i < n) :
j = 0
while (j < n) :
print(" ", maze[i][j], end = "")
j += 1
i += 1
print(end = "\n")
def printPath(self, maze, i, j, mid, result) :
if (i == mid and j == mid) :
# When we get middle row and middle column
self.status = True
print(result ,"(MID[", i ,"][", j ,"]) ")
return
if (maze[i][j] == 0) :
return
value = maze[i][j]
maze[i][j] = 0
if (j + value < len(maze)) :
# Move right
self.printPath(maze, i, j + value, mid, result + "["
+ str(i) + "]["
+ str(j) + "]⤑ ")
if (i + value < len(maze)) :
# Move down
self.printPath(maze, i + value, j, mid, result + "["
+ str(i) + "]["
+ str(j) + "]⤑ ")
if (j - value > 0) :
# Move left
self.printPath(maze, i, j - value, mid, result + "["
+ str(i) + "]["
+ str(j) + "]⤑ ")
if (i - value > 0) :
# Move Up
self.printPath(maze, i - value, j, mid, result + "["
+ str(i) + "]["
+ str(j) + "]⤑ ")
maze[i][j] = value
def printSolution(self, maze) :
n = len(maze)
self.status = False
self.printPath(maze, 0, 0, int(n / 2), "")
if (self.status == False) :
# No solution
print("\n No result ")
def main() :
task = Path()
# Odd square matrix
maze = [
[3, 1, 4, 2, 3],
[3, 2, 2, 1, 3],
[1, 3, 4, 3, 2],
[2, 3, 1, 1, 2],
[4, 2, 4, 3, 0]
]
# maze =
# [
# [ 3, 1, 4, 2, 3 ]
# [ 3, 2, 2, 1, 3 ]
# [ 1, 3, 4, 3, 2 ]
# [ 2, 3, 1, 1, 2 ]
# [ 4, 2, 4, 3, 0,]
# ]
# ------------------------
# Path =
# [
# [ 3, 1, -, 2, - ]
# [ -, 2, 2, 1, - ]
# [ -, 3, 4, 3, - ]
# [ -, -, 1, -, - ]
# [ -, -, -, -, -,]
# ]
# Solution ➀
# [0][0] ⤑ [0][3] ⤑ [0][1] ⤑ [1][1] ⤑
# [1][3] ⤑ [1][2] ⤑ [3][2] ⤑ (MID[2][2])
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# Path =
# [
# [ 3, 1, -, 2, - ]
# [ -, 2, -, -, - ]
# [ -, -, 4, -, - ]
# [ -, 3, 1, -, 2 ]
# [ -, -, -, -, -,]
# ]
# Solution ➁
# [0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑
# [3][4]⤑ [3][2]⤑ (MID[2][2])
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# Path =
# [
# [ 3, -, -, -, - ]
# [ -, -, -, -, - ]
# [ -, -, 4, -, - ]
# [ 2, -, 1, -, - ]
# [ -, -, -, -, -,]
# ]
# Solution ➂
# [0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# Path =
# [
# [ 3, -, -, -, - ]
# [ 3, 2, -, 1, 3 ]
# [ -, -, 4, -, - ]
# [ 2, 3, 1, -, 2 ]
# [ -, -, -, -, -,]
# ]
# Solution ➃
# [0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑
# [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# Path =
# [
# [ 3, -, -, -, - ]
# [ 3, 2, 2, 1, 3 ]
# [ -, -, 4, -, - ]
# [ 2, 3, 1, -, 2 ]
# [ -, -, -, -, -,]
# ]
# Solution ➄
# [0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑
# [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# Path =
# [
# [ 3, -, -, -, - ]
# [ 3, -, 2, 1, - ]
# [ -, -, 4, -, - ]
# [ 2, -, 1, -, - ]
# [ -, -, -, -, -,]
# ]
# Solution ➅
# [0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
task.printSolution(maze)
if __name__ == "__main__": main()
Output
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[ 2 ][ 2 ])
# Ruby Program for
# Find paths from corner cell to middle cell in maze
class Path
# Define the accessor and reader of class Path
attr_reader :status
attr_accessor :status
def initialize()
self.status = false
end
def display(maze, n)
i = 0
while (i < n)
j = 0
while (j < n)
print(" ", maze[i][j])
j += 1
end
i += 1
end
print("\n")
end
def printPath(maze, i, j, mid, result)
if (i == mid && j == mid)
# When we get middle row and middle column
self.status = true
print(result ,"(MID[", i ,"][", j ,"]) ", "\n")
return
end
if (maze[i][j] == 0)
return
end
value = maze[i][j]
maze[i][j] = 0
if (j + value < maze.length)
# Move right
self.printPath(maze, i, j + value, mid,
result + "[" + i.to_s + "][" + j.to_s + "]⤑ ")
end
if (i + value < maze.length)
# Move down
self.printPath(maze, i + value, j, mid,
result + "[" + i.to_s + "][" + j.to_s + "]⤑ ")
end
if (j - value > 0)
# Move left
self.printPath(maze, i, j - value, mid,
result + "[" + i.to_s + "][" + j.to_s + "]⤑ ")
end
if (i - value > 0)
# Move Up
self.printPath(maze, i - value, j, mid,
result + "[" + i.to_s + "][" + j.to_s + "]⤑ ")
end
maze[i][j] = value
end
def printSolution(maze)
n = maze.length
self.status = false
self.printPath(maze, 0, 0, n / 2, "")
if (self.status == false)
# No solution
print("\n No result ", "\n")
end
end
end
def main()
task = Path.new()
# Odd square matrix
maze = [
[3, 1, 4, 2, 3],
[3, 2, 2, 1, 3],
[1, 3, 4, 3, 2],
[2, 3, 1, 1, 2],
[4, 2, 4, 3, 0]
]
# maze =
# [
# [ 3, 1, 4, 2, 3 ]
# [ 3, 2, 2, 1, 3 ]
# [ 1, 3, 4, 3, 2 ]
# [ 2, 3, 1, 1, 2 ]
# [ 4, 2, 4, 3, 0,]
# ]
# ------------------------
# Path =
# [
# [ 3, 1, -, 2, - ]
# [ -, 2, 2, 1, - ]
# [ -, 3, 4, 3, - ]
# [ -, -, 1, -, - ]
# [ -, -, -, -, -,]
# ]
# Solution ➀
# [0][0] ⤑ [0][3] ⤑ [0][1] ⤑ [1][1] ⤑
# [1][3] ⤑ [1][2] ⤑ [3][2] ⤑ (MID[2][2])
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# Path =
# [
# [ 3, 1, -, 2, - ]
# [ -, 2, -, -, - ]
# [ -, -, 4, -, - ]
# [ -, 3, 1, -, 2 ]
# [ -, -, -, -, -,]
# ]
# Solution ➁
# [0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑
# [3][4]⤑ [3][2]⤑ (MID[2][2])
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# Path =
# [
# [ 3, -, -, -, - ]
# [ -, -, -, -, - ]
# [ -, -, 4, -, - ]
# [ 2, -, 1, -, - ]
# [ -, -, -, -, -,]
# ]
# Solution ➂
# [0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# Path =
# [
# [ 3, -, -, -, - ]
# [ 3, 2, -, 1, 3 ]
# [ -, -, 4, -, - ]
# [ 2, 3, 1, -, 2 ]
# [ -, -, -, -, -,]
# ]
# Solution ➃
# [0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑
# [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# Path =
# [
# [ 3, -, -, -, - ]
# [ 3, 2, 2, 1, 3 ]
# [ -, -, 4, -, - ]
# [ 2, 3, 1, -, 2 ]
# [ -, -, -, -, -,]
# ]
# Solution ➄
# [0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑
# [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# Path =
# [
# [ 3, -, -, -, - ]
# [ 3, -, 2, 1, - ]
# [ -, -, 4, -, - ]
# [ 2, -, 1, -, - ]
# [ -, -, -, -, -,]
# ]
# Solution ➅
# [0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
task.printSolution(maze)
end
main()
Output
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
/*
Scala Program for
Find paths from corner cell to middle cell in maze
*/
class Path(var status: Boolean)
{
def this()
{
this(true);
}
def display(maze: Array[Array[Int]], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < n)
{
print(" " + maze(i)(j));
j += 1;
}
i += 1;
}
print("\n");
}
def printPath(maze: Array[Array[Int]],
i: Int, j: Int, mid: Int, result: String): Unit = {
if (i == mid && j == mid)
{
// When we get middle row and middle column
this.status = true;
println(result + "(MID[" + i + "][" + j + "]) ");
return;
}
if (maze(i)(j) == 0)
{
return;
}
var value: Int = maze(i)(j);
maze(i)(j) = 0;
if (j + value < maze.length)
{
// Move right
printPath(maze, i, j + value, mid,
result + "[" + i.toString() + "][" + j.toString() + "]⤑ ");
}
if (i + value < maze.length)
{
// Move down
printPath(maze, i + value, j, mid,
result + "[" + i.toString() + "][" + j.toString() + "]⤑ ");
}
if (j - value > 0)
{
// Move left
printPath(maze, i, j - value, mid,
result + "[" + i.toString() + "][" + j.toString() + "]⤑ ");
}
if (i - value > 0)
{
// Move Up
printPath(maze, i - value, j, mid,
result + "[" + i.toString() + "][" + j.toString() + "]⤑ ");
}
maze(i)(j) = value;
}
def printSolution(maze: Array[Array[Int]]): Unit = {
var n: Int = maze.length;
this.status = false;
printPath(maze, 0, 0, n / 2, "");
if (this.status == false)
{
// No solution
println("\n No result ");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Path = new Path();
// Odd square matrix
var maze: Array[Array[Int]] = Array(
Array(3, 1, 4, 2, 3),
Array(3, 2, 2, 1, 3),
Array(1, 3, 4, 3, 2),
Array(2, 3, 1, 1, 2),
Array(4, 2, 4, 3, 0)
);
/*
maze =
[
[ 3, 1, 4, 2, 3 ]
[ 3, 2, 2, 1, 3 ]
[ 1, 3, 4, 3, 2 ]
[ 2, 3, 1, 1, 2 ]
[ 4, 2, 4, 3, 0,]
]
------------------------
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, 2, 1, - ]
[ -, 3, 4, 3, - ]
[ -, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➀
[0][0] ⤑ [0][3] ⤑ [0][1] ⤑ [1][1] ⤑
[1][3] ⤑ [1][2] ⤑ [3][2] ⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, -, -, - ]
[ -, -, 4, -, - ]
[ -, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➁
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑
[3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ -, -, -, -, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➂
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, -, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➃
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, 2, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➄
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, -, 2, 1, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➅
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
*/
task.printSolution(maze);
}
}
Output
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
import Foundation;
/*
Swift 4 Program for
Find paths from corner cell to middle cell in maze
*/
class Path
{
var status: Bool;
init()
{
self.status = false;
}
func display(_ maze: [[Int]], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < n)
{
print(" ", maze[i][j], terminator: "");
j += 1;
}
i += 1;
}
print(terminator: "\n");
}
func printPath(_ maze: inout[[Int]],
_ i: Int, _ j: Int, _ mid: Int, _ result: String)
{
if (i == mid && j == mid)
{
// When we get middle row and middle column
self.status = true;
print(result ,"(MID[", i ,"][", j ,"]) ",separator:"");
return;
}
if (maze[i][j] == 0)
{
return;
}
let value: Int = maze[i][j];
maze[i][j] = 0;
if (j + value < maze.count)
{
// Move right
self.printPath(&maze, i, j + value, mid,
result + "["
+ String(i) + "]["
+ String(j) + "]⤑ ");
}
if (i + value < maze.count)
{
// Move down
self.printPath(&maze, i + value, j, mid,
result + "["
+ String(i) + "]["
+ String(j) + "]⤑ ");
}
if (j - value > 0)
{
// Move left
self.printPath(&maze, i, j - value, mid,
result + "["
+ String(i) + "]["
+ String(j) + "]⤑ ");
}
if (i - value > 0)
{
// Move Up
self.printPath(&maze, i - value, j, mid,
result + "["
+ String(i) + "]["
+ String(j) + "]⤑ ");
}
maze[i][j] = value;
}
func printSolution(_ maze: inout[[Int]])
{
let n: Int = maze.count;
self.status = false;
self.printPath(&maze, 0, 0, n / 2, "");
if (self.status == false)
{
// No solution
print("\n No result ");
}
}
}
func main()
{
let task: Path = Path();
// Odd square matrix
var maze: [
[Int]
] = [
[3, 1, 4, 2, 3],
[3, 2, 2, 1, 3],
[1, 3, 4, 3, 2],
[2, 3, 1, 1, 2],
[4, 2, 4, 3, 0]
];
/*
maze =
[
[ 3, 1, 4, 2, 3 ]
[ 3, 2, 2, 1, 3 ]
[ 1, 3, 4, 3, 2 ]
[ 2, 3, 1, 1, 2 ]
[ 4, 2, 4, 3, 0,]
]
------------------------
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, 2, 1, - ]
[ -, 3, 4, 3, - ]
[ -, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➀
[0][0] ⤑ [0][3] ⤑ [0][1] ⤑ [1][1] ⤑
[1][3] ⤑ [1][2] ⤑ [3][2] ⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, -, -, - ]
[ -, -, 4, -, - ]
[ -, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➁
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑
[3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ -, -, -, -, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➂
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, -, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➃
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, 2, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➄
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, -, 2, 1, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➅
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
*/
task.printSolution(&maze);
}
main();
Output
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
/*
Kotlin Program for
Find paths from corner cell to middle cell in maze
*/
class Path
{
var status: Boolean;
constructor()
{
this.status = false;
}
fun display(maze: Array < Array < Int >> , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
var j: Int = 0;
while (j < n)
{
print(" " + maze[i][j]);
j += 1;
}
i += 1;
}
print("\n");
}
fun printPath(maze: Array < Array < Int >> ,
i: Int, j: Int, mid: Int, result: String): Unit
{
if (i == mid && j == mid)
{
// When we get middle row and middle column
this.status = true;
println(result + "(MID[" + i + "][" + j + "]) ");
return;
}
if (maze[i][j] == 0)
{
return;
}
val value: Int = maze[i][j];
maze[i][j] = 0;
if (j + value < maze.count())
{
// Move right
this.printPath(maze, i, j + value,
mid, result + "[" + i.toString() + "][" + j.toString() + "]⤑ ");
}
if (i + value < maze.count())
{
// Move down
this.printPath(maze, i + value, j,
mid, result + "[" + i.toString() + "][" + j.toString() + "]⤑ ");
}
if (j - value > 0)
{
// Move left
this.printPath(maze, i, j - value,
mid, result + "[" + i.toString() + "][" + j.toString() + "]⤑ ");
}
if (i - value > 0)
{
// Move Up
this.printPath(maze, i - value, j,
mid, result + "[" + i.toString() + "][" + j.toString() + "]⤑ ");
}
maze[i][j] = value;
}
fun printSolution(maze: Array < Array < Int >> ): Unit
{
val n: Int = maze.count();
this.status = false;
this.printPath(maze, 0, 0, n / 2, "");
if (this.status == false)
{
// No solution
println("\n No result ");
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Path = Path();
// Odd square matrix
val maze: Array < Array < Int >> = arrayOf(
arrayOf(3, 1, 4, 2, 3),
arrayOf(3, 2, 2, 1, 3),
arrayOf(1, 3, 4, 3, 2),
arrayOf(2, 3, 1, 1, 2),
arrayOf(4, 2, 4, 3, 0)
);
/*
maze =
[
[ 3, 1, 4, 2, 3 ]
[ 3, 2, 2, 1, 3 ]
[ 1, 3, 4, 3, 2 ]
[ 2, 3, 1, 1, 2 ]
[ 4, 2, 4, 3, 0,]
]
------------------------
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, 2, 1, - ]
[ -, 3, 4, 3, - ]
[ -, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➀
[0][0] ⤑ [0][3] ⤑ [0][1] ⤑ [1][1] ⤑
[1][3] ⤑ [1][2] ⤑ [3][2] ⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, 1, -, 2, - ]
[ -, 2, -, -, - ]
[ -, -, 4, -, - ]
[ -, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➁
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑
[3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ -, -, -, -, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➂
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, -, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➃
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, 2, 2, 1, 3 ]
[ -, -, 4, -, - ]
[ 2, 3, 1, -, 2 ]
[ -, -, -, -, -,]
]
Solution ➄
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑
[1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Path =
[
[ 3, -, -, -, - ]
[ 3, -, 2, 1, - ]
[ -, -, 4, -, - ]
[ 2, -, 1, -, - ]
[ -, -, -, -, -,]
]
Solution ➅
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
*/
task.printSolution(maze);
}
Output
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [0][3]⤑ [0][1]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [1][4]⤑ [1][1]⤑ [3][1]⤑ [3][4]⤑ [3][2]⤑ (MID[2][2])
[0][0]⤑ [3][0]⤑ [1][0]⤑ [1][3]⤑ [1][2]⤑ [3][2]⤑ (MID[2][2])
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