-7
\$\begingroup\$

I am writing a code which would return the path in a maze using recursion, but now with the path I also want the number of steps.

How do count number of steps in this program? or number of times this recursive function is called in my actual path?

I can't put the increment counter just inside the recursive function as it will also add the backtracked (unwanted) iterations.

This is my code.

public class Main {
// 0 - obstacle
// 1 - open space
// 2 - path taken
// 3 - goal 
private static int[][] maze = 
    {{0, 0, 1, 1, 1, 1, 1, 1},
    {2, 0, 1, 0, 0, 0, 1, 1},
    {1, 0, 1, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 0, 0, 0, 0},
    {0, 0, 1, 0, 1, 3, 1, 1},
    {0, 0, 1, 0, 1, 0, 0, 1},
    {1, 0, 1, 1, 1, 0, 0, 0},
    {1, 1, 1, 0, 1, 1, 0, 0}};
// use symbols to make reading the output easier...
// 0 - obstacle - '#'
// 1 - open space - '.'
// 2 - path taken - '+'
// 3 - goal - '*'
private static final char[] MAZE_SYMBOLS = {'#', '.', '+', '*' };


//Try to findPathFrom initial position if the maze is solved print the solution
public static void main(String[] args) {
    if (findPathFrom(1, 0)) {
        print();
    } else {
        System.out.println("no solution found");
    }
}

private static boolean findPathFrom(int row, int col) {

    // when we reach the goal we have solved the problem
    if (maze[row][col] == 3) {
        return true;
    }

    // add the position to our path changing its value to '2'
    maze[row][col] = 2;

    //try all available neighbours 
    //North (row-1, col), South (row+1, col), East (row, col+1) and West (row, col-1)
    // if any of these return true then we have solved the problem
    if (isAvailablePosition(row - 1, col) && findPathFrom(row - 1, col)) {
        return true;
    }
    if (isAvailablePosition(row + 1, col) && findPathFrom(row + 1, col)) {
        return true;
    }
    if (isAvailablePosition(row, col - 1) && findPathFrom(row, col - 1)) {
        return true;
    }
    if (isAvailablePosition(row, col + 1) && findPathFrom(row, col + 1)) {
        return true;
    }

    //If none of previous positions is valid or matches the goal, it is necessary to revert the 
    //temporary state. This reversal or backtrack is what gives name to the algorithm: backtracking
    maze[row][col] = 1;

    return false;
}

// A position is available if: (1) it is inside the bounds of the maze 
// (2) if it is an open space or (3) it is the goal 
private static boolean isAvailablePosition(int row, int col) {
    boolean result =  row >= 0 && row < maze.length
            && col >= 0 && col < maze[row].length
            && (maze[row][col] == 1 || maze[row][col] == 3);
            return result;
}

//print the output using MAZE_SYMBOLS
private static void print(){
    for(int row = 0; row < maze.length; ++row) {
        for(int col = 0; col < maze[row].length; ++col) {
            System.out.print(MAZE_SYMBOLS[maze[row][col]]);
        }
        System.out.println();
    }
}

}

Is there another method to do this?

\$\endgroup\$

closed as off-topic by chillworld, Quill, Mast, BCdotWEB, SuperBiasedMan Dec 17 '15 at 9:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – chillworld, Quill, Mast, BCdotWEB, SuperBiasedMan
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    \$\begingroup\$ I vote to close because you are actually asking for adding new functionality into the program. \$\endgroup\$ – chillworld Dec 17 '15 at 8:27
  • \$\begingroup\$ So, using this function I can't get number of steps? I need a new function? \$\endgroup\$ – user10859 Dec 18 '15 at 7:30
  • \$\begingroup\$ Code review doesn't stand for "upgrading" your code with new functionality, we review working code and give tips on how to improve your code. This can be in the topics of performance, coding style,... but never creating new functionality. \$\endgroup\$ – chillworld Dec 18 '15 at 7:49
1
\$\begingroup\$

Perhaps you could just count the number of 2 / + characters encountered as you loop through maze in print()? (Is this the value you were asking for?)

That has the advantage of not requiring any changes to your recursion.

The rest of your code looks fine to me, although an Enum for maze symbols could make the magic numbers (1, 2, 3) more readable.

\$\endgroup\$
  • \$\begingroup\$ That's what I want but without using a new function. In this function only can we make program count the actual number of steps? \$\endgroup\$ – user10859 Dec 18 '15 at 7:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.