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)
{
// 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])

*/
}
}``````

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()
{
// 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])

*/
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)
{
// 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])

*/
}
}``````

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

*/
}``````

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()
{
// 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])

*/
}
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()
{
// 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])

*/
}
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() :
#  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])

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_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()
#  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])
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])

*/
}
}``````

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()
{
// 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])

*/
}
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
{
// 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])

*/
}``````

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.

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.