# Counting number of steps while finding right path [closed]

Posted on

Problem

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?

Solution

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.