Programming Forums - Recursion Maze Question

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Java (http://www.programmingforums.org/forum17.html)

- - Recursion Maze Question (http://www.programmingforums.org/showthread.php?t=12106)

Recursion Maze Question

In my computer science class we solved mazes of 0s and 1s using recursion

1 0 0 0 0
1 1 0 1 0
0 1 1 0 1
1 0 1 1 1
0 0 1 0 1

you can only move from a 1 to a 1 and u have to get from the top left to the bottom right. I got the code to say whether or not you can get to the end of the maze, but for extra credit we are supposed to count the number of steps to get there. I was wondering if sum1 could help get in the right direction to counting the number of steps because i dont understand how you could do it since it would count all of the 1s that are connected.

Here is my code:

//Julian

//Recursion Maze

//Comp Sci II AP



import java.io.*;

import java.util.*;

public class recursion

{

        public static void main(String[] args) throws IOException

        {

                Scanner file=new Scanner(new File("recursion.txt"));

                int length=file.nextInt();

                int[][] maze=new int[length][length];

                for(int x=0;x<length;x++)

                {

                        for(int y=0;y<length;y++)

                        {

                                maze[x][y]=file.nextInt();

                        }

                }

                mazeSolver ms=new mazeSolver();

                ms.mazeSolver(maze);ms.solving(0,0);

                System.out.println(ms);

        }

}

class mazeSolver

{

        boolean exitFound=false;

        int[][] maze;

        public void mazeSolver(int[][] m)

        {

                maze=m;

        }

        public boolean solving(int r,int c)

        {

                if(r>=0&&c>=0&&r<maze.length&&c<maze.length&&maze[r][c]==1)

                {

                        maze[r][c]=2;

                        if(r==maze.length-1&&c==maze.length-1)

                        {

                                exitFound=true;

                        }

                        else

                        {

                                solving(r+1,c);

                                solving(r-1,c);

                                solving(r,c+1);

                                solving(r,c-1);

                        }

                }

                return exitFound;

        }

        public String toString()

        {

                String output;

                if(exitFound)

                {

                        output="Exit Found";

                }

                else

                {

                        output="Exit Not Found";

                }

                return output;

        }

        

}

and here is the data

the data should be named "recursion.txt", and the 5 gives you the dimensions of the maze

Quote:

Originally Posted by afroboy0731 (Post 120575)

I got the code to say whether or not you can get to the end of the maze, but for extra credit we are supposed to count the number of steps to get there. I was wondering if sum1 could help get in the right direction to counting the number of steps because i dont understand how you could do it since it would count all of the 1s that are connected.

If I'm understanding you correctly, it's easier than you might imagine. Imagine your recursive function like a tree, starting from a root and spreading out it's branches, with each branching point representing a step in the maze. Then the number of branching points for a particular branch would also give you the number of steps taken in the maze, would it not?

but if i did it like that then wouldnt i get 10 instead of the correct answer, 8

Quote:

Originally Posted by afroboy0731 (Post 120584)

but if i did it like that then wouldnt i get 10 instead of the correct answer, 8

Try it and see what happens. I can't answer that myself without punching it in.

Quote:

Originally Posted by afroboy0731 (Post 120584)

but if i did it like that then wouldnt i get 10 instead of the correct answer, 8

I see what you are saying, you could possibly, add some code to check another step ahead, and see if that 'branch' is a dead end, if it is then dont add that as a step.

Quote:

Originally Posted by kyndig (Post 121270)

I see what you are saying, you could possibly, add some code to check another step ahead, and see if that 'branch' is a dead end, if it is then dont add that as a step.

No need. Seeing how old this post is, I don't suppose it would hurt for me to give a more exact answer to the problem. Essentially, with each recursive step you'd pass in a variable that would record the "depth" of that step. So instead of "solving(r+1,c)" you'd use, "solving(r+1,c,depth+1)". Then, when you find the exit, just return the depth. If the exit isn't found, return 0 or -1.

In Python, you'd do something like this:

def load_maze(filename):
    file = open(filename)
    length = file.readline()
    maze = [[int(x) for x in line.split()] for line in file]
    file.close()
    return maze
 
def solve_maze(maze):
    def explore(x, y, depth):
        if len(maze) == (y + 1) and len(maze[y]) == (x + 1):
             return depth
 
        try: value = maze[y][x]
        except IndexError: return 0
 
        if value == 0: return 0
 
        return explore(x + 1, y, depth + 1) or
               explore(x - 1, y, depth + 1) or
               explore(x, y + 1, depth + 1) or
               explore(x, y - 1, depth + 1)
 
    return explore(0, 0, 1)
 
solution = solve_maze(load_maze("recursion.txt"))
 
if solution:
    print "End of maze reached in %d steps" % solution
else:
    print "No solution"

Won't that try to or two integers together if there is more than one solution to the maze?

Quote:

Originally Posted by The Dark (Post 121317)

Won't that try to or two integers together if there is more than one solution to the maze?

Yes, but in Python a boolean "or" means returning the first object considered "True". For instance:

>>> 0 or False or "" or 3 or 5

3

The code doesn't find the fastest route, but does return the number of steps in the first route it finds.

Thanks Arevos, I didn't know that.