Find paths from corner cell to middle cell in maze
The problem at hand involves finding paths from the corner cells of a given maze to the middle cell of the maze. The maze is represented as a square matrix, where each cell contains a non-negative integer representing the number of steps you can take from that cell. The objective is to find all possible paths from each corner cell to the middle cell.
Problem Statement and Description
Given a square matrix representing a maze, the task is to find all possible paths from each corner cell to the middle
cell. You can move in four directions: right, down, left, and up. The value in each cell indicates the number of
steps you can take in that direction. The goal is to reach the middle cell (located at maze.length/2
,
maze.length/2
) starting from each corner cell.
Example
Consider the following maze:
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 ],
]
See the result:
[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])
Idea to Solve the Problem
To solve this problem, we can use a recursive approach. We start from each corner cell and recursively explore all possible paths by moving in the directions indicated by the value in the current cell. We mark visited cells to avoid cycles and backtrack when no further movement is possible.
Pseudocode
Here's a high-level pseudocode for the solution:
function findPaths(maze):
for each corner cell (i, j) in maze:
if corner cell is not visited:
explorePaths(maze, i, j, middleIndex)
function explorePaths(maze, i, j, mid):
if current cell is out of bounds or visited:
return
if (i, j) is middle cell:
print the current path
return
mark current cell as visited
value = maze[i][j]
explorePaths(maze, i + value, j, mid)
explorePaths(maze, i - value, j, mid)
explorePaths(maze, i, j + value, mid)
explorePaths(maze, i, j - value, mid)
unmark current cell
function main():
maze = initialize the maze
findPaths(maze)
main()
Explanation
The pseudocode outlines the main approach. We start from each corner cell and explore all possible paths recursively,
backtracking when necessary. The explorePaths
function moves in the four directions, marking cells as
visited and unmarking them when backtracking. When the middle cell is reached, the current path is printed.
Code Solution
/*
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])
Time Complexity
The time complexity of this algorithm depends on the number of possible paths in the maze. In the worst case, each cell can be visited only once, leading to a time complexity of O(N^2) where N is the size of the maze's side. However, due to backtracking and early stopping, the actual number of recursive calls might be significantly less than this upper bound.
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