Help on a maze program

[lauheiyeung]

Hi guys, I'm currently taking my first programming course
there is a maze program that I cannot figure it out what should I do to check if there is a path. I haven't learnt things like struct and class.Please give me some advice. Below is the question:

Question: Write a program to find a path in a maze using recursion. A maze is an n by n square of cells each of which is either blocked or clear. Your program starts at the top left corner and tries to find a path (of clear cells) leading to the lower right corner. Each move is either horizontally (left or right) or vertically (up or down) but never diagonally. Note that a path may not exist.
The maze is represented by a two-dimensional bool array, where true means blocked and false means clear. Your program should ask the user to input the size of the maze followed by the maze row by row. Your program should also maintain another char array to record the path found (if there is one) and print it out at the end of processing. Your program should work for mazes of sizes between 4 and 20.
One simple way to find a path is at each step: try moving along one of the allowable directions and try another direction if that one fails. If no possible path can be found, fall back to the previous step and try another path. Note that a move is not allowed if the cell to be moved into is either blocked or that it is outside of the maze. Note also that our simple method may loop in “circles” inside the maze and needs to be augmented so that it will not get into an infinite loop.

  #include<iostream>

using namespace std;



int main(){
        
        int input=0;
        
        for (;input<4 || input>20;){
        cout << "Please input size of maze (a number between 4 and 20 is expected) -> ";
        cin >> input;
                
        if (input<4 || input>20)
        cout << "**Error** maze size is not in range!\n";
        }

        
        int maze[input-1][input-1];
        
        cout << "Please input contents of maze row by row. 1 for barrier and 0 for free passage.\n\n";
        
        for (int i=0;i<input;i++){
                for (int n=0;n<input;n++){
                cin >> maze[i][n];
                }
        }
        
        if ((maze[0][1]==1 && maze[1][0]==1)||(maze[0][0]==1)){
        cout << "**Error** entrance to maze is blocked!\n";
        return 0;
        }
        
        int h = input -1;
        int v = input -1;
        

        
        for (long t=0;(h>0 || v>0)&&(t<input*input);t++){
                if (maze[h-1][v] == 0)
                h=h-1;
                else if (maze[h][v-1] == 0)
                v=v-1;
                else if ((h<input-1)&& maze[h][v] == 0)
                h=h+1;
                else if ((v<input-1)&& maze[h][v] == 0)
                v=v+1;
        }

        
        if (v==0 && h==0)
        cout << "The maze and the path:\n";
        else cout << "**Warning** no path from entrance to exit!\n" << "The maze and the path:\n";
        
        cout << "+";
        for (int q=0;q<input;q++)
        cout << "-";
        cout << "+\n";
        
        //HERE THE FUNCTION OF PRINTING THE MAZE
        
        cout << "+";
        for (int q=0;q<input;q++)
        cout << "-";
        cout << "+\n";
}

[anup30]

challenging problem.

[AbstractionAnon]

Line 20: That's not valid C++. In C++, array sizes must be known at compile time.

Line 20: Your instructions state "The maze is represented by a two-dimensional bool array" maze is not a bool array.

Instructions also state: find a path in a maze using recursion. I see no recursion in your program.

Your program should also maintain another char array to record the path found
For each cell you traverse, you want to record the direction traveled (L,R,U,D). I don't see any record of the path you traversed.

General idea: Create a bool function that explores the four possible paths from the current position. As each adjacent cell is explored, record the direction in the history array. If the next cell is out of bounds or blocked, return false and erase the direction traveled from the history array. If the path is clear to the next cell in a direction, call the bool function recursively to explore the possible cells that position. If the bool function reaches the end cell, return true and pop up one level of recusrion. If the bool function can't move in any direction, return false, pop up one level of recursion and remove the direction traveled from the history array. If the top level call to the bool function returns true, you have found a path through the maze and the path should in the history array.