Currently I am trying to solve a program that determines whether it is possible to solve a maze and if the maze is solvable it should print out the number of steps to go through the maze path. The starting position and the end position and the maze are given in a input file in the following format:
Line 1: test cases(N)
For each N lines the first line will contain size of the maze, the start position and the end exit location will be given. Then a visual depiction of the maze will also be present in the input file
For example the sample input for this challenge is:
3
6 7 0 0 5 6
1110111
1011101
1001001
1011101
1000001
1111110
3 3 2 0 0 2
111
110
111
5 5 1 0 3 1
01111
11001
01001
01001
01111
The excact rules of the maze are that the 0s are inpenetrable walls and the 1s are free walking space being able to move around. Also the end position is not marked by any special character but rather the location is given to us.
The following code is my approach to the challenge which is obviously not functional:
import java.io.*;
import java.util.*;
public class Maze
{
public static void main(String[] args) throws FileNotFoundException
{
Scanner sc = new Scanner(new File("maze.txt"));
int tc = sc.nextInt();
for(int p = 0; p < tc; p++ ) {
int rows = sc.nextInt();
int cols = sc.nextInt();
int startRow = sc.nextInt();
int startCol = sc.nextInt();
int endRow = sc.nextInt();
int endCol = sc.nextInt();
sc.nextLine();
char[][] maze = new char[rows][cols];
for(int i = 0; i < rows; i++) {
String s = sc.nextLine();
for(int j = 0; j < cols; j++) {
maze[i][j] = s.charAt(j);
}
}
if(solvable(maze,startRow,startCol,endCol,endRow)) {
int count = 0;
for(char[] arr : maze) {
for(char elem: arr) {
if(elem == 'x') count++;
}
}
System.out.println("It takes " + count + " steps to solve the maze");
}else {
System.out.println("Unsolvable");
}
}
}
public static boolean solvable(char[][] maze,int row, int col,int finishRow, int finishCol) {
if(row < 0 || col < 0 || row >maze.length - 1 || col > maze[0].length - 1) {
return false;
}
if(row == finishRow && col == finishCol) {
return true;
}
if(maze[row][col] == 0) {
return false;
}
char c = maze[row][col];
maze[row][col] = 'x';
if(solvable(maze,row + 1,col,finishRow,finishCol)) {
return true;
}
if(solvable(maze,row - 1,col,finishRow,finishCol)){
return true;
}
if(solvable(maze,row ,col + 1,finishRow,finishCol)) {
return true;
}
if(solvable(maze,row,col - 1,finishRow,finishCol)) {
return true;
}
maze[row][col] = c;
return false;
}
}
As seen by the title this program produces a stack overflow error. I am incorporating the general algorithm for solving a maze and not incorporating the flood fill alogorithm. I need to identify the flaw in my recursive method solvable. Please note that this is a competetive programming enviorment so coding from the object oriented side of java would be inconvinient.
The problem is the infinite recursion in solvable. Why is that?
Why it never terminates?
Let's take a closer look at how it works:
return false if the position is invalidreturn true if the position is the targetreturn false if the position is the start
'x'Where's the flaw in this logic?
When is the marking 'x' used? -> Ha!
If the marking 'x' is not used, what's going to happen? -> Ha!
Imagine this is the maze, and the algorithm always checks the path going down first before checking other directions:
#####
#S E#
# ###
# ###
#####
The algorithm will first go from S until the bottom. At the bottom there is a way to go up, so it goes one step up. There, there is a way to go down, so it goes back down. And it gets stuck going up and down forever.
So the solution is to use the 'x' markings to avoid exploring the same positions forever.